题目要求必须恰好装满,那你就输出动态规划后求出的f[weight],如果f[weight]没被更新过,就输入no solution.
如果题目说可以不装满,就输出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 dofor j := weight-w[i] downto 0 doif (f[j]+p[i] > f[j+w[i]]) thenf[j+w[i]] := f[j] + p[i];if (f[weight] = 0) then writeln('No Solution.') else writeln(f[weight]);