I am doing a programming exercise as below:
There are a box and a list of items.
The box has a fixed size. Each item has its own size and price.
We can put as many items as we want in the box if the sum of items' size is smaller than the size of the box. (Each item can only be put once).
Find the combination of items that can be put in the box with the highest price.

box: size = 10
| item | size | price |
| ---- | ---- | ----- |
| 1    | 8    | 4     |
| 2    | 10   | 5     |
| 3    | 1    | 2     |

In this case, the answer will be 6 because item 1 and 3 are selected, price 4 2 = 6 (sum of sizes is 8 which is below 10)

My approach is to perform a backtracking to find all possible combinations and record the highest price, but I am not sure if it is efficient enough if there is a huge number of items on the list.

Is there any approach that is more efficient?

CodePudding user response：

This is exactly the 0/1 knapsack problem. Indeed trying all combinations will solve the problem, but it will take impossibly long for more than, say, 50 items.

The problem is NP-complete, but it can be solved pseudo-polynomially. That is, it can be solved efficiently if the total size of the box is relatively small.

CodePudding user response：

Yes, there is an approach that is more efficient !

Dynamic Programming - Bottom Up

Approach: Instead of brute forcing the solution by evaluating all possible subsets, you can instead solve the problem iteratively for each item at each weight. Take this Example:
Let there be four items i[1,2,3,4] with associated weights w[5,3,4,2], values v[60,50,70,30] and a maximum weight W = 5.

We will now construct a 2D value array, which saves the maximum value when choosing a certain item a a certain weight, V[i][w].

The algorithm to fill the array is:

V[i][w] = max(V[i-1, w], V[i-1, w - w_i] v_i) OTHERWISE V[i-1, w]

What does this do ? :
For each item at each weight, we look first if we can even choose the item without exceeding the weight limit. If not, we take the value of the item above at that weight (or 0 if that item also cannot be chosen).

The interesting stuff happens if we can choose the item. If so, if choosing the item is greater than the value if choosing the item above, we choose the current item instead:
(So if V[i-1, w] < V[i-1, w - w_i] v_i)

Do this for all n items and w weights and you will get the highest possible value. This would be the Matrix when executing the algorithm on the mentioned example:

See Item 4 column at weight 5. Choosing item 3 at weight 5 gives us a maximum value of 70. We can however, look at the alternative of choosing item 4 and looking at the value at that weight for item 3. At item 3, we can see we choose the value of the item above for a value of 50. So the solution is choosing item 4 and 2.

The complexity of running this is O(N * W) as compared to O(2 ^ N) of the brute force approach.