首页 > 其他分享 >动态规划之分组的背包问题

动态规划之分组的背包问题

时间:2023-06-30 21:11:59浏览次数:48  
标签:背包 .. 每组 问题 分组 物品 动态

问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

算法

这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值,则有:

f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}

使用一维数组的伪代码如下:

for 所有的组k
    for v=V..0
        for 所有的i属于组k
            f[v]=max{f[v],f[v-c[i]]+w[i]}

注意这里的三层循环的顺序,甚至在本文的第一个beta版中我自己都写错了。“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

另外,显然可以对每组内的物品应用P02中“一个简单有效的优化”。

小结

分组的背包问题将彼此互斥的若干物品称为一个组,这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题(例如P07),由分组的背包问题进一步可定义“泛化物品”的概念,十分有利于解题。

标签:背包,..,每组,问题,分组,物品,动态
From: https://www.cnblogs.com/shoshana-kong/p/17517822.html

相关文章

  • 动态规划之混合三种背包问题
    问题如果将P01、P02、P03混合起来。也就是说,有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。应该怎么求解呢?01背包与完全背包的混合考虑到在P01和P02中给出的伪代码只有一处不同,故如果只有两类物品:一类物品只能取一次,另一类......
  • vue:<img>动态绑定的路径无法解析问题
    问题我们引用图片,正常的静态img图片是这么引用的<imgsrc="@/assets/img/icoms/people.png"/>没问题,只要路径正确在vue中动态绑定路径:src<img:src="@/assets/img/icoms/people.png"/>发现图片根本加载不出来,因为:src根本不能解析@/assets/img/icoms/people.png解决......
  • 动态规划01
    动态规划核心要义这一步的数据依据上一步或者上两步的数据动态规划五部确定dp数组(dptable)以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组动态规划第一题斐波那契数列dp[i]表示第i个数列的值递推公式已经给出f(n)=f(n-1)+f(n-2)初始化已......
  • 第三讲 多重背包问题
    题目有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。基本算法这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物......
  • 带负载转矩观测器的永磁同步电动机控制方法。 负载转矩观测器无论是对静态的负载变化
    带负载转矩观测器的永磁同步电动机控制方法。负载转矩观测器无论是对静态的负载变化还是动态的负载变化都有很好的观测效果。一方面可以较好的跟踪负载转矩的变化,另一方面可以作为前馈减小电机转速的波动。原创文章,转载请说明出处,资料来源:http://imgcs.cn/5c/672148599043.html......
  • day114- 动态sql
    动态SQL解决拼接SQL语句字符串时的问题。if标签if标签可通过test属性的表达式进行判断,若表达式的结果为true,则标签中的内容会执行;反之标签中的内容不会执行<!--List<Emp>getEmpByCondition(Empemp);--><selectid="getEmpByCondition"resultType="com.gu.mybatis.poj......
  • 第一讲 01背包问题
    题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值......
  • jdk动态代理
    一、Class.forName的作用classc=Class.forName(“com.xxx.Example”); 返回的是一个类的实例factory=(ExampleInterface)c.newInstance();  newInstance之前必须保证类被加载了jvm在装载类时会执行类的静态代码段,要记住静态代码是和class绑定的,class装载成功就表示执行......
  • 动态规划十大经典案例
    动态规划十大经典案例动态规划是一种常用的算法思想,它可以解决很多优化问题,比如求最大值、最小值、最长子序列等。动态规划的基本思想是把一个复杂的问题分解成若干个子问题,然后从最简单的子问题开始,逐步推导出更大的子问题的解,最终得到原问题的解。动态规划通常需要定义一个状态......
  • leetcode动态规划-
    什么是动态规划动态规划的定义和特点动态规划的基本思想和步骤动态规划的分类和常见问题线性动态规划最长公共子序列最长递增子序列最大子数组和区间动态规划矩阵链乘法括号化问题背包动态规划0-1背包问题完全背包问题多重背包问题状态压缩动态规划......