UC知道PASCAL01背包问题~高手进
来源：百度知道 编辑：UC知道 时间：2024/06/03 02:22:40
01背包问题，那个最核心的部分看不来啊~
for i:=1 to n do
for x:=m downto w[i] do
if f[x-w[i]]+c[i]>f[x] then f[x]:=f[x-w[i]]+c[i];
这样怎么就行了！！？？
复制的就不用拉..
for i:=1 to n do
for x:=m downto w[i] do
if f[x-w[i]]+c[i]>f[x] then f[x]:=f[x-w[i]]+c[i];
这样怎么就行了！！？？
复制的就不用拉..
原方程:dp[i,x]:=max(dp[i-1,x-w[i]]+c[i])
所以空间可以压缩到一维
但为了保证一维时dp[i]用的是dp[i-1]的结果,就必须downto
求最大权值的:if f[x-w[i]]+c[i]>f[x] then f[x]:=f[x-w[i]]+c[i];
部分循环:for i:=1 to n do
for x:=m downto w[i] do
f[i]表示i的体积能得到的最大价值。