To obtain the ideal solution the sum of all possible combinations of K
weights adjacent to one another must give the same value of sum. In order
to achieve such a condition, the elements of all possible K combinations
must remain the same.
Eg : Consider the following set of weights where K = 2
W = [ 1 , 2 , 1 , 4 , 3 , 2 ]
The possible sums with K = 2 are 1 + 2 = 3 , 2 + 1 = 3 , 1 + 4 = 5 , 4 + 3 = 7 and 3 + 2 = 5 .
All other combinations will have weights that are not close to one another.
In order for all the possible combinations to give the same value of sum all the sets of
K = 2 taken in order must have the same weights.
Therefore this ideal set would have the form
W = [ 1 , 2 , 1 , 2 , 1 , 2] ; K = 2 and SUM = 3 FOR ALL COMBINATIONS
Ie the number of minimum possible exchanges would be 2. All other possibilities of
making an ideal set of weights would have an even greater number of exchanges required.
So to find the number of exchanges required we can simply consider K sets ( W1
,W 2 , … , WK) in which each set would have the weights that are present in the
same repeated position according to the order given to Tarun when summing up
In the above example the two sets would be :
W1 = [1 , 1 , 3] and W2 = [2 , 4 , 2]
After obtaining these sets we can convert all the values present in each of these sets to
the value that has the highest frequency in each set
Ie in W1 we can see that
Frequency of 1 = 2 and
Frequency of 3 = 1.
Therefore exchanging 3 with a weight of 1 from the infinite set of available weights will
allow us to accomplish the same.
And by converting the weight 4 in set W2 to 2 we can do the same there as well.
So in a total of 2 exchanges we can reach the required ideal set that has the sum as a
single value.
Therefore by considering the frequency of weights in each of the K sets and by
taking the sum of required exchanges in each set . We can find out the required
number of exchanges needed to reach the solution.