Question

c++背包问题输出装入背包的物品序号

请问一下 c++背包问题，怎么输出装入背包的物品序号? 高手指点一下，谢谢。

Answer 1

一般的动态规划解最优值你应该会吧...
如果不会请上网搜背包九讲..看01背包那部分

现在来讲讲如何得到方案
明显地，背包的状态转移方程式是
f(i,j)=max{f(i-v[j],j-1),f(i,j-1)}
表示i的体积，装前j的物品所能得到的最大值
在程序中我们以opt[i][j]来储存
现在我们可以再定义一个数组last[i][j]，类型为整数
明显地..一个f(i,j)的值一定来自于f(k,j-1),k=i或i-v[j]
那么.我们可以在求某一个opt[i][j]时，把k存入last[i][j]
这样.我们最终会得到一条从没装到装完的路径
通过last[V][N](最终态)
我们可以向上不断回溯以得知方案