M Sach - 1 year ago 37

Java Question

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.

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)

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

`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 Source

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];
}
```