• 售前

  • 售后

热门帖子
入门百科

【动态规划】01背包标题

[复制链接]
123457783 显示全部楼层 发表于 2022-1-16 10:45:51 |阅读模式 打印 上一主题 下一主题
01背包题目



有一个背包,容量4磅,现有如下为物品:
物品重量代价吉他(G)11500音响(S)43000电脑(L)32000在不超出容量,且装入物品不重复的情况下让背包中的代价最大
思绪分析:
使用动态规划来办理。
每次遍历到第i个物品,根据w,v来确定是否必要将该物品装入背包,即给定n个物品,设v,w分别为第i个物品的代价和重量。
C为背包的容量,再令v [j]体现前i个物品中可以大概装入容量为j的背包中的最大代价,则我们有下面效果:
  1. 行是i,列是j
  2. 1. val[i][0] = val[0][j] =0;        //表示填入表的第一行,第一列都为0
  3. 2. w[i]>j        ->        val[i][j] = val[i-1][j];        //当准备加入新增的商品容量大于当前背包的容量,则直接使用上一单元格的策略
  4. 3. j>=w[i]        ->        val[i][j] = max{val[i-1]][j], val[i-1][j-w[i]]+v[i]};        //当准备加入的新增的商品小于等于当前背包容量
  5. /*装入的方式:
  6. val[i-1][j]: 上一单元格存入的最大价值
  7. v[i]:当前商品的价值
  8. val[i-1][j-w[i]]:装入i-1商品,到剩余空间j-w[i]的最大价值
  9. */
复制代码
填表过程:
假设分别存在容量为0,1,2,3,4的背包
物品i\j0123400000吉他(G)01500(G)1500(G)1500(G)1500(G)音响(S)01500(G)1500(G)1500(G)3000(S)电脑(L)01500(G)1500(G)2000(L)3500(G+L)

  • 假设如今只有吉他(G),不管背包多大,只能放一个吉他
  • 假设如今有吉他和音响,由于当背包小于4时,只能放吉他,但是当背包巨细为4时音响代价大于吉他,以是正在背包中放入音响。
  • 假设如今有吉他,音响和电脑,在背包为3时,电脑代价高于吉他以是放入电脑,而背包为4时,既可以放入吉他和电脑,也可以单独放入音响,G+L>S,因此选择放入吉他和电脑。
办理01背包题目标重要抓手是筹划表格,进而筹划状态转换方程,肯定要注意动态规划的根本在于状态转换,基于某种条件判断,在办理下一个子题目标时间是否必要转换状态。
办理动态规划题目总结:

  • 筹划初始状态
  • 分析标题得到状态条件,写状态转换方程
  • 写代码
  1. int[] w = {1, 4, 3};    //背包中装入的物品的重量
  2. int[] v = {1500, 3000, 2000};   //装入物品的价值
  3. int m= 4;   //背包承受的重量
复制代码
二维数组体现

[code]public static void two_diversity(int[] w,int[] v,int m){        /*        行是i,列是j        1. v[0] = v[0][j] =0;        //体现填入表的第一行,第一列都为0        2. w>j        ->        v[j] = v[i-1][j];        //当准备加入新增的商品容量大于当前背包的容量,则直接使用上一单位格的计谋        3. j>=w        ->        v[j] = max{v[i-1]][j], v[i-1][j-w]+v};        //当准备加入的新增的商品小于便是当前背包容量        //装入的方式:        v[i-1][j]: 上一单位格存入的最大值        v:当前商品的代价        v[i-1][j-w]:装入i-1商品,到剩余空间j-w的最大值        */        int n = v.length;   //全部物品的个数        //创建二维数组        //v:当前商品的代价        //w:当前商品的重量        //val[j]:当前的前i个物品中可以大概装入容量为j的背包中的最大代价        int[][] val = new int[n+1][m+1];        //初始化第一行第一列        for (int i = 0;i

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作