动态规划 0/1背包问题(续) 求思路 怎么判断有没有装满
动态规划 0/1背包问题(续) 求思路 怎么判断有没有装满
【动态规划】0/1背包问题（续）
Time Limit:1000MS Memory Limit:65536KTotal Submit:119 Accepted:43
Description给定n种物品和一背包.物品i的重量是w[i],其价格是p[i],背包的容量为weight.
问:应该如何选择装入背包的物品,使得刚好装满背包时物品的总价值最大?
在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品 Input输入共四行.
第一行为背包容量weight；
第二行为物品件数n；(n
题目要求必须恰好装满,那你就输出动态规划后求出的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]);