w[i],v[i],c[i],分别表示第i种物品的价值，代价，数目, 已知限制为j（对价值，代价，数目的限制都有可能，这里我们只讨论代价的限制）,问题是，在满足限制的前提下，怎么选择，可以得到的价值最大
dp[j]=max(dp[j],dp[j-kv[i]]+kw[i]) 0<=k<=c[i] && k*v[i]<=j 这种情况需要三重循环，复杂度较高很多情况下行不通
对与第i种物品（v[i],w[i],c[i]）我们分两种情况讨论 1.如果c[i]v[i]>=j时，不可能出现i物品全部用光的情况,此时可看作完全背包求解dp[j] 2.否则，把c[i]分解，例如7=1+2+4,13=1+2+4+6,把 c[i]=1+2+4…+k,把 kw[i],k*v[i] 看成一种物品且数目为1,这样就可以看作01背包处理,分别求解dp[j]. 理由：对于i物品的选择个数有0~c[i]方案,对于1个i物品，2个i物品，，，k个i物品的选择有2^k种选择，这些方案里包含0-c[i]方案, 所以这两种方法是等价的 以下是网上找的代码
#include <stdio.h> #define Max(a, b) (a > b ? a : b) int dp[1005][10005]; int k[1005], value[1005], cnt[1005]; int main(int argc, char *argv[]) { int i, j, s; scanf("%d %d", &i, &j); for (int ind = 1; ind <= i; ++ind) scanf("%d %d %d", &k[ind], &value[ind], &cnt[ind]); for (int ind = 1; ind <= i; ++ind) { for (int jnd = 1; jnd <= j; ++jnd) { if (jnd - k[ind] < 0) dp[ind][jnd] = dp[ind - 1][jnd]; else { s = dp[ind - 1][jnd]; for (int knd = 1; knd * k[ind] <= jnd && knd <= cnt[ind]; knd++) s = Max(s, dp[ind - 1][jnd - knd * k[ind]] + knd * value[ind]); dp[ind][jnd] = s; } } } printf("%d\n", dp[i][j]); return 0; }