0-1背包问题 àì夳堔傛蜴生んèń 2022-05-30 01:20 74阅读 0赞 问题:有n个物品,第i个物品价值为vi,重量为wi,其中vi和wi均为非负数,背包的容量为W,W为非负数。现需要考虑如何选择装入背包的物品,使装入背包的物品总价值最大。该问题以形式化描述如下: 目标函数为 : ![1364096225_6763.jpg][] 约束条件为:![1364096448_8646.jpg][] 满足约束条件的任一集合(x1,x2,...,xn)是问题的一个可行解,问题的目标是要求问题的一个最优解。考虑一个实例,假设n=5,W=17, 每个物品的价值和重量如表9-1所示。可将物品1,2和5装入背包,背包未满,获得价值22,此时问题解为你(1,1,0,0,1)。也可以将物品4和5装入背包,背包装满,获得价值24,此时解为(0,0,0,1,1)。 ![1364096951_8384.jpg][] 下面根据动态规划的4个步骤求解该问题。 (1) 刻画0-1背包问题的最优解的结构。 可以将背包问题的求解过程看作是进行一系列的决策过程,即决定哪些物品应该放入背包,哪些物品不放入背包。如果一个问题的最优解包含了物品n,即xn=1,那么其余x1,x2,...,x(n-1)一定构成子问题1,2,...,n-1在容量W-wn时的最优解。如果这个最优解不包含物品n,即xn=0,那么其余x1,x2,...,x(n-1)一定构成子问题1,2,...,n-1在容量W时的最优解。 (2)递归定义最优解的值 根据上述分析的最优解的结构递归地定义问题最优解。设c\[i,w\]表示背包容量为w时,i个物品导致的最优解的总价值,得到下式。显然要求c\[n,w\]。 ![1364126887_3091.jpg][] 状态转移方程: if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); else m[i][j]=m[i-1][j]; [1364096225_6763.jpg]: https://img-my.csdn.net/uploads/201303/24/1364096225_6763.jpg [1364096448_8646.jpg]: https://img-my.csdn.net/uploads/201303/24/1364096448_8646.jpg [1364096951_8384.jpg]: https://img-my.csdn.net/uploads/201303/24/1364096951_8384.jpg [1364126887_3091.jpg]: https://img-my.csdn.net/uploads/201303/24/1364126887_3091.jpg
相关 01背包问题 [0-1背包问题][0-1] Reference: https://www.jianshu.com/p/a66d5ce49df5 问题描述: 0-1背包问题:给定 ﹏ヽ暗。殇╰゛Y/ 2022年10月11日 13:40/ 0 赞/ 259 阅读
相关 01背包问题 1.题目 有N件物品和一个容量为V的背包。第i件物品的成本是c\[i\],价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大,要求是:物品只能放一次。 2.分 系统管理员/ 2022年09月10日 11:27/ 0 赞/ 220 阅读
相关 背包问题-背包01-苹果 package 动态规划.背包01; import java.util.Scanner; public class 苹果 \{ static class 野性酷女/ 2022年07月12日 12:12/ 0 赞/ 260 阅读
相关 01背包问题 ![Center][] ![Center 1][] [Center]: /images/20220616/e1a67e5ed0214bac8ec5293bc2b54 ╰+攻爆jí腚メ/ 2022年06月16日 14:46/ 0 赞/ 240 阅读
相关 01背包问题 public class package0_1 { int V[][] = new int[200][200];//物品选取,背包承重 int max( 约定不等于承诺〃/ 2022年06月08日 06:15/ 0 赞/ 245 阅读
相关 01背包问题 【例9.11】01背包问题 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 一个旅行者有一个最多能装M公斤的背包,现在有n件物 淩亂°似流年/ 2022年06月08日 03:59/ 0 赞/ 240 阅读
相关 背包问题—01背包、完全背包 01背包问题 题目 有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。 思路 这 末蓝、/ 2022年05月30日 10:10/ 0 赞/ 371 阅读
相关 01背包问题 简单背包问题 设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn。 问能否从这n件物品中选择若干件放入背包中,使得放入的重量之和正好为S 痛定思痛。/ 2022年05月26日 12:18/ 0 赞/ 239 阅读
相关 01背包问题 转载:[https://blog.csdn.net/xp731574722/article/details/70766804][https_blog.csdn.net_xp73 怼烎@/ 2022年05月06日 15:00/ 0 赞/ 295 阅读
相关 背包问题01 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c\[i\],价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题,特 左手的ㄟ右手/ 2022年01月29日 11:34/ 0 赞/ 329 阅读
还没有评论,来说两句吧...