Knapsack Problem: bags have variable weights

Question

Consider a list of weights and a list of bags with variable weights. I need an algorithm that finds the minimum number of bags needed to store all weights.

Simply sorting in decreasing order doesn't work. Consider this example:

weights = [8,7,4,4]
bags = [16,7,5,5]

If we start inserting the weights in decreasing order, we end up with:

1st bag (capacity of 16): [8,7]
2nd bag (capacity of 7): [4]
3rd bag (capacity of 5): [4]

Whereas the optimal solution is:

1st bag: [8,4,4]
2nd bag: [7]

Answer 1

This problem can be considered as a variant of the Bin packing problem.

The bin packing is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used.

The problem is NP-hard, and various (exponential-time) exact algorithms have already been proposed for it (here). One simple way to solve the problem instance you described (in an exact manner) is to model it as an integer linear program:

% weights = [8,7,4,4]
% bags = [16,7,5,5]   
         
array[1..4,1..4] of  var 0..1: x;
array[1..4] of  var 0..1: y;

constraint x[1,1]+x[1,2]+x[1,3]+x[1,4] = 1;
constraint x[2,1]+x[2,2]+x[2,3]+x[2,4] = 1;
constraint x[3,1]+x[3,2]+x[3,3]+x[3,4] = 1;
constraint x[4,1]+x[4,2]+x[4,3]+x[4,4] = 1;
constraint 8*x[1,1]+7*x[2,1]+4*x[3,1]+4*x[4,1] <= 16 * y[1];
constraint 8*x[1,2]+7*x[2,2]+4*x[3,2]+4*x[4,2] <= 7 * y[2];
constraint 8*x[1,3]+7*x[2,3]+4*x[3,3]+4*x[4,3] <= 5 * y[3];
constraint 8*x[1,4]+7*x[2,4]+4*x[3,4]+4*x[4,4] <= 5 * y[4];

solve minimize y[1] + y[2] + y[3] + y[4];

The first four constraints indicate that each item has to be placed in exactly one bin, and the second four constraints are in fact capacity constraints. As you can see, the variables y[1], y[2], y[3], y[4] are all boolean. The variable y[i] indicates that whether or not the i-th bin is employed. I solved the model by the Gecode solver in MiniZinc. One optimal solution is:

x = array2d(1..4, 1..4, [1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]);
y = array1d(1..4, [1, 1, 0, 0]);

The solution says that we have to place the the item of weight 8, the items of weight 4 in the first bin, and the item of weight 7 in the second bin.