An overview of the

Given a set of items, each item has its own weight and value, the existing backpack, can bear a limited weight, in the restricted weight, take a number of items, making the total value of the maximum. This kind of problem is called the backpack problem.

01 Backpack Problem

Currently there are N items and a backpack of volume V. We know that the volume of item I is c_i, and the value is w_i. Since there is only one item of each kind, we can only choose to put it or not, which is called the 01 backpack problem. Now you need to pick a number of items that add up to as much value as possible, as long as they don’t add up to more than V. 1. Define the status DP [I][J]: the maximum value of the first I item, if the weight does not exceed J 2. Write the state transition equation: 3. coding!

	    memset(dp, 0.sizeof(dp)); / / initialization
	    for(int i = 1; i <= N; i++)
	        for(int j = 0; j <= V; j++){    // Make sure the boundary starts at 0
			       if(j >= c[i]) 
				     dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
	             else 
	                dp[i][j] = dp[i - 1][j];
	        }
Copy the code

Time complexity: O(NV)

The optimization of knapsack problem

It’s hard to optimize in time, but there’s a lot of double counting in space. Carefully observe the above state transition equation, for DP [I][j], only dp[i-1] layer is needed, and since it is [j-c[I]], we can know that we need to use a certain dp on the left continuously, starting from this property. Using a one-dimensional array DP [J] to represent the maximum value when the current weight does not exceed J, the state transition equation can be obtained

For (int I = 1; i <= n; ++i) for (int j = v; j >= c[i]; –j) dp[j] = max(dp[j – c[i]] + w[i], dp[j]);

Multiple backpack problem

There are N items, the ith item has a volume of C [I] and a value of w[I], and each item has a finite number of N [I]. For the existing backpack with a capacity of V, please put a number of items into it and make the total value as large as possible under the condition that the total volume does not exceed V.

Conversion 01 Backpack:N [I] items are split in turn and converted into 01 knapsack problem solution with time complexity of O(V ∑n). The transfer equation is as follows

The code is as follows:

	for (int i = 1; i <= N; i++) 
	    for (int j = 0; j <= V; j++) 
	        for (int k = 0; k <= n[i]; k++) 
	            if (j >= c[i] * k) 
	                dp[i][j] = max(dp[i - 1][j - c[i] * k] + w[i] * k, dp[i][j]);
	                If k=0, dp[I -1][j] =0, dp[I -1][j] =0
Copy the code

Spatially optimized version

	for (int i = 1; i <= N; i++) 
	    for (int j = V; j >= 0; j--) 
	        for (int k = 0; k <= n[i]; k++) 
	            if (j >= c[i] * k)
	                dp[j] = max(dp[j - c[i] * k] + w[i] * k, dp[j]);
Copy the code

Binary optimized version:

Using 1, 2, 4, 8, 16 can form any integer from 1 to 63. Taking advantage of this property, assuming that the ith item has n[I] items, we divide it into groups of 1, 2, 4, 8… 2^(k-1), n[I]-2^k+1, where k is the largest integer where n[I]-2^k+1 > 0. It can be proved that any number from 1 to N can be formed by the combination of several groups. So instead of the enumeration from 0 to n[I], the complexity of the enumeration is reduced to O(V sigma logn).

	// Find the maximum k
	    int ncnt = 1;
	    for(int i = 1; i <= N; ++i){
	        int k;
	        for(k = 1; n[i]-(1<<k)+1 > 0; ++k){
	            nc[ncnt] = (1<<(k- 1))*c[i];
	            nw[ncnt] = (1<<(k- 1))*w[i];
	            ++ncnt;
	        }
	        // Check if there are any left
	        --k;
	        nc[ncnt] = (n[i]-(1<<k)+1)*c[i];
	        nw[ncnt] = (n[i]-(1<<k)+1)*w[i];
	        ++ncnt;
	    }
	    / / 01 knapsack
	    for(int i = 1; i <= ncnt; ++i){
	    	for(int j = V; j >= nc[i]; --j){
	            dp[j] = max(dp[j], dp[j-nc[i]]+nw[i]); }}Copy the code

Complete backpack problem

Currently there are N kinds of items. The ith kind of item has a volume of C [I] and a value of w[I]. The number of each item is unlimited and you can choose any number of items. For the existing backpack with a capacity of V, please put some items into it so that the total volume does not exceed V and the total value is as large as possible. This is the problem with the full backpack, the difference between the 01 backpack and the infinite number of items.

Convert to 01 knapsack solution:

	for (int i = 1; i <= N; i++) 
	    for (int j = 0; j <= V; j++) 
	        for (int k = 0; k * c[i] <= j; k++) 
	            dp[i][j] = max(dp[i - 1][j - c[i] * k] + w[i] * k, dp[i][j]);
Copy the code

Time optimization algorithm:

In fact, since the number of each item is infinite, we don’t need to worry about the problem of dp[I][j-c[I]] being updated any more, because it is updated immediately, we can put the corresponding number in the next round

01 knapsack with difference only lies in the dp [I] [j – c [I]] and dp [I – 1] [j – c [I]] (01 knapsack), the time complexity O (NV)

	for (int i = 1; i <= n; i++) 
	    for (int j = 0; j <= v; j++) {
	        if (j >= c[i]) 
	            dp[i][j] = max(dp[i][j - c[i]] + w[i], dp[i - 1][j]);
	        else 
	            dp[i][j] = dp[i - 1][j];
	    }
Copy the code

Spatial optimization:

	for (int i = 1; i <= n; i++) 
	    for (int j = c[i]; j <= v; j++){
			dp[j] = max(dp[j], dp[j-c[i]]+w[i]);
Copy the code

It can be seen that at the end of the optimization, there is only a difference in order with 01 backpack

subtotal

An interesting detail of the knapsack problem: after optimization to one dimension, if the initial DP [1-n] is all 0, the final DP [I] means that the total weight does not exceed the maximum value of M; If only dp[0] is initialized to 0 and the rest is -INF, then dp[I] means the maximum value when the total weight is exactly I