动态规划 0/1背包问题(续) 求思路 怎么判断有没有装满
发布网友
发布时间：2022-04-22 15:48
共1个回答
热心网友
时间：2022-04-22 17:18
如果题目说可以不装满，就输出f[0..weight]中的最大值。
动态规划的过程：
1.枚举每种物品i
2.枚举j=weight->0，用f[ j ]+p[ i ]去更新f[ j + w[ i ] ]，由于是01背包，所以要倒着枚举
有问题请追问追问不装满的我懂，主要是要装满的还是没听懂 什么叫
输出动态规划后求出的f[weight]，如果f[weight]没被更新过，就输入no solution。
追答装满的更简单呢，直接输出f[weight]就可以了。
f数组是记录最大价值的，f[ i ]表示容量恰好为i的背包能装多大价值，动态规划的过程，就是用每种物品去更新这个f数组。看看上面写的过程，大概代码就是：
for i := 1 to n do
for j := weight-w[i] downto 0 do
if (f[j]+p[i] > f[j+w[i]]) then
f[j+w[i]] := f[j] + p[i];
if (f[weight] = 0) then writeln('No Solution.') else writeln(f[weight]);
