Dynamic Programming: Knapsack with Multiple Contstraits
Have N Kinds of items and a capacity are V Backpack.
First i There are at most si Pieces, the volume of each piece is vi, The value is wi.
Solve which items are loaded into the backpack, so that the total volume of the items does not exceed the capacity of the backpack, and the total value is the largest.
Output the maximum value.
Input format Two integers in the first line,N, V ( 0 < N≤ 1000, 0 < V≤ 20000 ), Separated by spaces, respectively indicate the number of objects and the volume of the backpack.
Next there is N Lines, three integers per line vi,wi,si, Separated by spaces, indicating the first i The volume, value, and quantity of various items.
Output format Output an integer that represents the maximum value.
data range 0 < N≤ 1000 0 < V≤ 20000 0 <vi,wi,si≤ 20000
Sample Input:
4 5
1 2 3
2 4 1
3 4 3
4 5 2
Sample Output:
10
Solution 1
Monotonous queue of multiple backpacks
dp[i][j] represents the maximum value that can be obtained when only the first i items are considered and the backpack capacity is j
Transfer formula: dp[i][j] = max(dp[i-1][j], dp[i-1][j-kc] + kw), 1≤k≤s = max(dp[i- 1][j-kc] +kw), 0≤k≤s
The transfer table is as follows:
When only considering dp[2][1]
Green means: backpack capacity v% item space c = 0
Orange means: backpack capacity v% item space c = 1
Green is only updated from the upper layer of green, and orange is only updated from the upper layer of orange
Only consider the transfer process of green blocks
Green represents the effective area, and gray represents the ineffective area (because it can only be moved backwards, or the number of items is limited). The limit on the number of items can also be understood as having at most s+1 elements in each row.
The black font represents the maximum value of the line
The process in the above figure can be achieved through a monotonic queue
Look at the transfer process from another perspective The dotted line represents the invalid transfer caused by the limit on the number of items
The solid line represents effective transfer
Red represents the maximum transfer
got the answer
Another angle of the complete knapsack problem The transition diagram of the complete knapsack problem is the same as that of the multiple knapsacks. However, there is no limit on the number of items, so it is not a sliding window situation, and there is no need for a monotonous queue. Only save a maximum value.
It is not necessarily all transferred by dp[1][0], but the example happens to be so
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010;
int dp[N], pre[N], q[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
memcpy(pre, dp, sizeof(dp));
int v, w, s;
cin >> v >> w >> s;
for (int j = 0; j < v; ++j) {
int head = 0, tail = -1;
for (int k = j; k <= m; k += v) {
if (head <= tail && k - s*v > q[head])
++head;
while (head <= tail && pre[q[tail]] - (q[tail] - j)/v * w <= pre[k] - (k - j)/v * w)
--tail;
if (head <= tail)
dp[k] = max(dp[k], pre[q[head]] + (k - q[head])/v * w);
q[++tail] = k;
}
}
}
cout << dp[m] << endl;
return 0;
}
Solution 2: Recursive DP
Imagine that we had a magical function knapsack(item,weight,volume) that could return the largest valid value of items that could be taken given the item number, weight and volume.
The solution would then iterate though every item after it and see what the answer would be and take the largest one. Similar to the 1/0 DP that you do.
However, you realize that you don’t need to keep track of the volume in the dp array hence it being only 2D.
You only need to keep track of the volume at the end when you see that there are no more items that can be taken.
A pretty standard solution for 1/0 Knapsack with a slight modification using recursive DP.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int knapsack(int item, int weight, int volume) {
// See if we have calculated this item before
if (dp[item][weight] == -1) {
// Set initial value to -2 (invalid result)
int max = -2;
// Iterate though all items past current item
for (int i = item; i < n; i++) {
// Make sure we don't go over max weight
if (weight + w[i] <= W_max) {
// Get the result of taking ith item
int res = knapsack(i + 1, weight + w[i], volume + vol[i]);
// Make sure result is valid (Total volume is greater than Vol_min)
if (res != -2) {
// If the result is valid take the max
max = Math.max(res + val[i], max);
}
}
}
// No other items taken and over Vol_min
if (max == -2 && volume >= Vol_min)
dp[item][weight] = 0;
else // Eveything else
dp[item][weight] = max;
}
// Return the value
return dp[item][weight];
}