动态规划 0/1背包问题(续) 求思路 怎么判断有没有装满【动态规划】0/1背包问题(续)Time Limit:1000MS Memory Limit:65536KTotal Submit:119 Accepted:43 Description给定n种物品和一背包.物品i的重量是w[i],其价
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/28 12:56:03
![动态规划 0/1背包问题(续) 求思路 怎么判断有没有装满【动态规划】0/1背包问题(续)Time Limit:1000MS Memory Limit:65536KTotal Submit:119 Accepted:43 Description给定n种物品和一背包.物品i的重量是w[i],其价](/uploads/image/z/6889556-20-6.jpg?t=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92+0%2F1%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%28%E7%BB%AD%29+%E6%B1%82%E6%80%9D%E8%B7%AF+%E6%80%8E%E4%B9%88%E5%88%A4%E6%96%AD%E6%9C%89%E6%B2%A1%E6%9C%89%E8%A3%85%E6%BB%A1%E3%80%90%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E3%80%910%2F1%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%EF%BC%88%E7%BB%AD%EF%BC%89Time+Limit%3A1000MS+Memory+Limit%3A65536KTotal+Submit%3A119+Accepted%3A43+Description%E7%BB%99%E5%AE%9An%E7%A7%8D%E7%89%A9%E5%93%81%E5%92%8C%E4%B8%80%E8%83%8C%E5%8C%85.%E7%89%A9%E5%93%81i%E7%9A%84%E9%87%8D%E9%87%8F%E6%98%AFw%5Bi%5D%2C%E5%85%B6%E4%BB%B7)
动态规划 0/1背包问题(续) 求思路 怎么判断有没有装满【动态规划】0/1背包问题(续)Time Limit:1000MS Memory Limit:65536KTotal Submit:119 Accepted:43 Description给定n种物品和一背包.物品i的重量是w[i],其价
动态规划 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背包问题(续) 求思路 怎么判断有没有装满【动态规划】0/1背包问题(续)Time Limit:1000MS Memory Limit:65536KTotal Submit:119 Accepted:43 Description给定n种物品和一背包.物品i的重量是w[i],其价
题目要求必须恰好装满,那你就输出动态规划后求出的f[weight],如果f[weight]没被更新过,就输入no solution.
如果题目说可以不装满,就输出f[0..weight]中的最大值.
动态规划的过程:
1.枚举每种物品i
2.枚举j=weight->0,用f[ j ]+p[ i ]去更新f[ j + w[ i ] ],由于是01背包,所以要倒着枚举
有问题请追问