M Sach M Sach - 4 months ago 7
Java Question

Is this similar to knapsack or Change-making algorithm?


this problem involves trying to fit items of
different weights into a bag so that the bag ends up with a
specified total weight or closest to total specified weight.


Example 1 :-
Bag can hold max up to 240 kg of weight


Item1- 60kg, Item2- 30kg, Item3- 55kg,Item4- 60kg,Item5- 80kg, Item6- 40kg, Item7- 7kg,

Here selected item should be Item1, Item4, Item5 and Item6(60+60+80+40 = 240 kg)

Example 2 :-
Bag can hold max up to 180 kg of weight


Item1- 60kg, Item2- 30kg, Item3- 55kg,Item4- 30kg,Item5- 70kg, Item6- 48kg

Here selected item should be Item1, Item4, Item5 and Item6(60+70+48 = 178 kg)

which is closest to 180 kg

Here is my template method

public List getSelectedItems(List<Presentation> inputList, int knapsackCapacity){
List selectItems;

// optimized algorith which returns selectItems and inputList containing the
//left out items i.e which are not selected;

return selectItems;
}


Some people on net call it simplest form of Knapsack problem as it does not have any benifit/profit associated with it and some call it Change-making problem

Whatever category it comes under i could not get algorithm for this and hence not able to make java program out of it. Any help here ?

Answer

This problem can be solved optimally in pseudo-polynomial time (O(nW)) using Dynamic Programming. What you have to do is modify a little the solution for Knapsack 0/1 like this:

if w[i] > W
    m[i,W] = m[i-1,W]
else if W - m[i-1, W] < W - m[i-1, W - w[i]] + w[i]
    m[i,W] = m[i-1,W]
else
    m[i-1, W - w[i]] + w[i]

Where W is the weight limit, w is the array of element weights. The difference is that you have to minimize the difference between W and the result, instead of maximizing the sum of the values.

Here is the wikipedia solution with the required modifications:

// Input:
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for j from 0 to W do
  m[0, j] := 0  // Initialize to 0
end for 
for i from 1 to n do    // for every element in the array
  for j from 0 to W do  // for every possible weight
    if w[i] > j then    // if the element's weight is higher than the max
      m[i, j] := m[i-1, j]  // use the solution that excludes the element
    // else if the diff between the solution that excludes the element and max weight
    // is smaller than the one that uses it, use the former.
    else if (j - m[i-1, j]) < (j - m[i-1, j - w[i]] + w[i])
      m[i, j] := m[i-1, j]
    // else use the element's weight in the solution
    else
      m[i, j] := m[i-1, j - w[i]] + w[i]
    end if

The 2D array m, is the memoization table, at the end of the algorithm, m[k, p] holds the best solution for elements from 0 to k with maximum weight p.

EDIT: I implemented and tested it in C++, it should be easy to port to Java:

template<typename T>
long Weight(const T& w, int size, const int W)
{
    vector<vector<int>> m(size+1, vector<int>(W+1, 0));

    for(int i = 1; i <= size; ++i)
    {
        for(int j = 0; j <= W; ++j)
        {
            if(w[i-1] > j)
            {
                m[i][j] = m[i-1][j];
            }
            else if((j - m[i-1][j]) < (j - (m[i-1][j - w[i-1]] + w[i-1])))
            {
                m[i][j] = m[i-1][j];
            }
            else
            {
                m[i][j] = m[i-1][j - w[i-1]] + w[i-1];
            }
        }
    }

    return m[size][W];
}