蒟蒻球助！01背包问题

这个空间优化下就好了吧
for i:=1 to n do
for j:=m downto v[i] do
f[j]:=max(f[j-v[i]]+value[i],f[j])

球这样如何搞出方案？

f[m]

神犇只言片语令吾等蒟蒻理解不能啊！
求详细讲解！！

球最大价值的我也会啊……
主要是方案不会搞啊……

建一维数组f[]，大小 = m;
f[i]表示可否用那些物品达到i的质量
然后循环~2层
1:循环i(f[i]能不能达到)
2:循环物品(j)(f[i+j]可以达到)
于是就完了

方案在哪里啊同学们？？？？

方案的话加一个path数组~~记录上一次最优方案，最后回溯一下就行了

同学，一维的空间怎么搞？

for i:=1 to n do
for j:=m downto v[i] do
if f[j-v[i]]+value[i]]>f[j] then begin
f[j]:=f[j-v[i]]+value[i]];
path[j]:=i;
end;


同学 这样显然是不对的

你去看背包九讲吧