M Sach - 1 year ago 65
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 ?

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];
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download