有N种物品和承重为W的背包,每种物品只有一件,每个物品都有对应的重量weight[i]和价值value[i],如何装使价值最大。
tab[i][j] = max(tab[i-1][j-weight[i]]+value[i],tab[i-1][j]) ({i,j|0<i<=n,0<=j<=W})
int f[w+1]; //f[x] 表示背包容量为x 时的最大价值
for (int i=0; i<n; i++)
for (int j=w; j>=size[i]; j--)
f[j] = max(f[j], f[j-size[i]]+value[i]);
每种物品都有无限件可用。
tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);({i,j|0<i<=n,0<=j<=total})
for (int i=0; i<n; i++)
for (int j=size[i]; j<=w; j++)
f[j] = max(f[j], f[j-size[i]]+value[i]);
就是每件物品给出确定的件数,求可得到的最大价值