用一维写的代码。 01背包:   for(j = 1;j <= n;j++)                      for(i = v;i <= 0;i++)                           f[i] = max(f[i],f[i-c[j]]+d[j]);   完全背包:   for(j = 1;j <= n;j++)                      for(i = 0;i <= v;i++)                           f[i] = max(f[i],f[i-c[v]]+d[i]);     两个背包只差在内循环的顺便。因为如果是正着数的话，f[j][i]的状态就会由f[j][i-c[j]]来推导得。 显然f[j][i-c[j]]是已经进入第j种物品的子结果，这是不符合01背包的，而应该是无限背包的。

评论