作业帮 > 数学 > 作业

动态规划 0/1背包问题(续) 求思路 怎么判断有没有装满

来源：学生作业帮 编辑：搜搜做题作业网作业帮 分类：数学作业 时间：2024/07/12 16:52:26
动态规划 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
动态规划 0/1背包问题(续) 求思路 怎么判断有没有装满
题目要求必须恰好装满,那你就输出动态规划后求出的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 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]);
求动态规划0/1背包问题的经典习题及测试数据 动态规划的0-1背包问题,请高手解释下代码 0-1背包问题的多种解法代码（动态规划、贪心法、回溯法、分支限界法） 求PASCAL背包问题和无限背包思路和程序 求一道动态规划题的解答思路以及状态方程 分别用贪心算法和动态规算法求解0/1背包问题的最优解和最大收益 第二个问题怎么求.没有思路. 背包问题的算法登上算法、递归算法、贪婪算法、动态规划算法利用matlab编程实现我把我仅有的分都给了 用动态规划,分治法,回溯发,分枝限界法解下列0-1背包为题例题:n=3,w=[100,14,10],p=[20,18,1 lingo求0-1规划问题 0-1背包问题的测试数据 数学建模中规划的分类时常有什么线性规划和非线性规划 动态规划 非动态规划 多目标规划 单目标规划 到底该怎么具体的给数学