按照 挑战程序设计竞赛书里的方法推导如下
dp[i][j] 前i个物品体积为j
(1) dp[i+1][j] = max{dp[i][j-k*v[i]] + k * w[i] | 0 <= k <= m[i] && j - k * v[i] >=0 }
(2) 假设 a[j] = dp[i][j*v[i]]
(3) 假设 b[j] = a[j] - j * w[i]
dp[i+1][ (j+k) * v[i] ] = max {b[j], b[j+1], ... , b[j+k]} + (j+k) * w[i]
推理过程
根据(1) 展开 dp[i+1][ (j+k) * v[i] ]
dp[i+1][ (j+k) * v[i] ] = max{ dp[i][ ( j ) * v[i] ] + (k-0) * w[i],
dp[i][ (j+1) * v[i] ] + (k-1) * w[i],
dp[i][ (j+2) * v[i] ] + (k-2) * w[i],
...
dp[i][ (j+k) * v[i] ] + (k-k) * w[i] }
把式子(2)代入
dp[i+1][ (j+k) * v[i] ] = max{ a[j+0] + (k-0) * w[i],
a[j+1] + (k-1) * w[i],
a[j+2] + (k-2) * w[i],
...
a[j+k] + (k-k) * w[i] }
变形:先减去 (j+n) * w[i] 然后加上 (j+n) * w[i], 0 <= n <= k
dp[i+1][ (j+k) * v[i] ] = max{ a[j+0] - (j+0) * w[i] + (j+0) * w[i] + (k-0) * w[i] ,
a[j+1] - (j+1) * w[i] + (j+1) * w[i] + (k-1) * w[i] ,
a[j+2] - (j+1) * w[i] + (j+2) * w[i] + (k-2) * w[i] ,
...
a[j+k] - (j+1) * w[i] + (j+k) * w[i] + (k-k) * w[i] }
用式子(3) 代入 , 并且 (j+n) * w[i]+ (k-n) * w[i] = (j+k) * w[i]
dp[i+1][ (j+k) * v[i] ] = max{ b[j+0] + (j+k) * w[i],
b[j+1] + (j+k) * w[i],
b[j+2] + (j+k) * w[i],
...
b[j+k] + (j+k) * w[i] }
就可以得到 dp[i+1][ (j+k) * v[i] ] = max {b[j], b[j+1], ... , b[j+k]} + (j+k) * w
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
const int N = 20010;
int v[N], w[N], s[N];
int n, V;
int dp[N];
int deq[N+1];
int deqv[N+1];
int main() {
scanf("%d%d", &n, &V);
for (int i = 0; i < n; i++) scanf("%d%d%d", &v[i], &w[i], &s[i]);
for (int i = 0; i < n; i++) {
for (int a = 0; a < v[i]; a++) { //余数
int hh = 0, tt = -1; // deque 重置
for (int j = 0; j * v[i] + a <= V; j++) { //j是个数
int val = dp[j * v[i] + a] - j * w[i]; // b[j]
if(hh <= tt && deq[hh] < j - s[i]) hh++;//滑动窗口长度为s[i] + 1,若超出长度 s[i] + 1 就缩
while(hh <= tt && deqv[tt] <= val) tt--;
deq[++tt] = j;
deqv[tt] = val;
dp[j * v[i] + a] = deqv[hh] + j * w[i];
}
}
}
printf("%d", dp[V]);
return 0;
}