01背包问题 系统管理员 2022-09-10 11:27 219阅读 0赞 # 1.题目 # 有N件物品和一个容量为V的背包。第i件物品的成本是c\[i\],价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大,要求是:物品只能放一次。 # 2.分析 # 写动态规划题,需要抓住三点:做好状态假设;并推导出转换条件; 假设`dp[i][j]` 表示放当前第i件物品,在总质量为j的情况下,可以得到的最大价值,当前物品只有放与不放两种选择,如果选择放,那么就相当于从j个质量中腾出w\[i\]个质量给第i个物品;如果选择不放,那么就相当于直接“继承”第i-1件物品的最大值。 所以根据上面这两点,我们可以得到如下表达式: d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j \] i f ( j < w \[ i \] ) d p \[ i − 1 \] \[ j − w \[ i \] \] + c \[ i \] i f ( j ≥ w \[ i \] ) dp\[i\]\[j\]=\\left\\\{\\begin\{aligned\} &dp\[i-1\]\[j\] \\quad \\quad if(j < w\[i\])\\\\ &dp\[i-1\]\[j-w\[i\]\]+c\[i\] \\quad if(j \\ge w\[i\]) \\end\{aligned\} \\right. dp\[i\]\[j\]=\{ dp\[i−1\]\[j\]if(j<w\[i\])dp\[i−1\]\[j−w\[i\]\]\+c\[i\]if(j≥w\[i\]) 根据这个式子,就可以写出整个代码了。 # 3.示例 # 各个物品的重量w = \[1,3,2,5\],各个物品的金钱p = \[200,240,140,150\],背包所能承受的最大重量 5。那么所能得到的最大价值是什么? # 4.代码 # def pack_01(w,c,maxW): # f = [0 for i in range(4) for j in range(5)] # 生成的是一位数组 # 第一个是行,第二个是列 f = [[0 for _ in range(6)] for _ in range (5)] for i in range(1,5): # i表示当前物品 [1,5) for j in range(1,maxW+1): # j表示当前重量 [5,0) f[i][j] = f[i-1][j] # 首先初始化赋值,这是最基本的 if j >= w[i]: f[i][j] = max(f[i][j],f[i-1][j-w[i]] + c[i]) # 取最大 print(f[4][maxW]) # 为了方便,0下标被置为0 w = [0,1,3,2,5] c = [0,100,240,140,150] maxW = 5 # 能承受的最大重量 pack_01(w,c,5)
相关 01背包问题 [0-1背包问题][0-1] Reference: https://www.jianshu.com/p/a66d5ce49df5 问题描述: 0-1背包问题:给定 ﹏ヽ暗。殇╰゛Y/ 2022年10月11日 13:40/ 0 赞/ 256 阅读
相关 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 赞/ 259 阅读
相关 01背包问题 ![Center][] ![Center 1][] [Center]: /images/20220616/e1a67e5ed0214bac8ec5293bc2b54 ╰+攻爆jí腚メ/ 2022年06月16日 14:46/ 0 赞/ 237 阅读
相关 01背包问题 public class package0_1 { int V[][] = new int[200][200];//物品选取,背包承重 int max( 约定不等于承诺〃/ 2022年06月08日 06:15/ 0 赞/ 244 阅读
相关 01背包问题 【例9.11】01背包问题 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 一个旅行者有一个最多能装M公斤的背包,现在有n件物 淩亂°似流年/ 2022年06月08日 03:59/ 0 赞/ 239 阅读
相关 背包问题—01背包、完全背包 01背包问题 题目 有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。 思路 这 末蓝、/ 2022年05月30日 10:10/ 0 赞/ 369 阅读
相关 01背包问题 简单背包问题 设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn。 问能否从这n件物品中选择若干件放入背包中,使得放入的重量之和正好为S 痛定思痛。/ 2022年05月26日 12:18/ 0 赞/ 236 阅读
相关 01背包问题 转载:[https://blog.csdn.net/xp731574722/article/details/70766804][https_blog.csdn.net_xp73 怼烎@/ 2022年05月06日 15:00/ 0 赞/ 292 阅读
相关 背包问题01 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c\[i\],价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题,特 左手的ㄟ右手/ 2022年01月29日 11:34/ 0 赞/ 329 阅读
还没有评论,来说两句吧...