pascal 01背包怎么知道选了哪几项?

发布网友发布时间：2024-09-06 00:07

共3个回答

热心网友时间：2024-10-27 00:19

背包方程f[i,j]:=max{f[i-1,j],f[i-1,j-w[i]]+v[i]}
我们设g[i,j]为记录类型，表示转移到f[i,j]的上一步的j的值，即：
若f[i,j]=f[i-1,j] 则g[i,j]:=j;
若f[i,j]=f[i-1,j-w[i]] 则g[i,j]:=j-w[i];
这个过程在动态规划主过程里实现。

之后用dfs
search(n,m);
深搜每一层时判断g[x,y]是等于y还是等于y-w[x]，若前者则此物品选了，后者则此物品没有选。然后后序输出即可。
附深搜(现编，意会~具体细节你自己去弄弄吧)

procere search(x,y:longint);
begin
if x=0 then exit;
if g[x,y]=y-w[i] then begin search(x-1,y-w[i]);write(x,' ');end else search(x-1,y);
end;

热心网友时间：2024-10-27 00:19

指针，或者b数组里辨析

热心网友时间：2024-10-27 00:19

我用Boolean数组超空间似的存储状态b[i,j,k]表示f[i,j]时第k个物体选不选，
超猥琐的哈希，在vijos上AC，不过超内存了（vijos的评测机强）