创建软件网站,个人域名 公司网站,如何让百度收录,苏州房地产网站建设概念
背包问题#xff08;Knapsack Problem#xff09;是算法领域的经典组合优化问题#xff0c;在资源分配等场景有广泛应用#xff0c;以下从定义、常见类型、解决方法等方面介绍#xff1a;
定义
给定一组物品#xff0c;每个物品都有自己的重量和价值#xff0c;…概念
背包问题Knapsack Problem是算法领域的经典组合优化问题在资源分配等场景有广泛应用以下从定义、常见类型、解决方法等方面介绍
定义
给定一组物品每个物品都有自己的重量和价值在限定背包容量的情况下如何选择物品放入背包使得装入背包的物品总价值最大同时不超过背包的容量限制。
常见类型
|0 - 1 背包问题每个物品只有取或不取两种状态1 表示取0 表示不取不能取部分物品。例如有多个不同重量和价值的宝石背包容量有限决定选取哪些宝石能获得最大价值。
|完全背包问题每个物品可以无限次选取。比如商店里有不同价格和体积的商品购物袋容量固定考虑每种商品购买多少件能使总价值最高。
|多重背包问题每个物品有一定的数量限制只能在数量范围内选取。像仓库里有不同类型且数量有限的货物卡车运载量有限决定装载哪些货物能实现最大收益。 0-1背包
问题描述
有(N)件物品和一个容量为(V)的背包。每件物品有两个属性第(i)件物品的费用占用背包的容量是(c(i))价值是(w(i))。需要求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量且价值总和最大。
问题特点
每种物品只有一件可以选择放或者不放不存在取部分物品的情况这也是 “0 - 1” 的含义0 代表不放1 代表放。
算法基本思想
通常利用动态规划思想求解。
定义子问题(f(i)(v))表示前(i)件物品放入一个容量最多为(v)的背包可以获得的最大价值。 其状态转移方程为(f(i)(v)max{f(i - 1)(v),f(i - 1)(v - c(i)) w(i)}) 。该方程的含义是“将前(i)件物品放入容量为(v)的背包中” 这一问题若只考虑第(i)件物品放或者不放可转化为只涉及前(i - 1)件物品的问题
|不放第(i)件物品问题转化为 “前(i - 1)件物品放入容量为(v)的背包中”此时最大价值为(f(i - 1)(v)) 。
|放第(i)件物品问题转化为 “前(i - 1)件物品放入剩下的容量为(v - c(i)\)的背包中”此时能获得的最大价值是(f(i - 1)(v - c(i)))再加上放入第(i)件物品获得的价值(w(i)) 。 (f(i)(v))的值取上述两种情况中的最大值。按照这个方程递推完毕后最终的答案是(f(N)(V))如果我们定义的子问题是前(i)件物品放入一个容量恰好为(v)的背包可以获得的最大价值那么答案是(f(N)(0..V))中的最大值因为(f(i)(v))有意义当且仅当存在一个前(i)件物品的子集其费用总和为(v) 。 引例 分析
这是一道以故事为背景的算法问题。主人公辰辰梦想成为伟大医师为拜师医师带他到满是草药的山洞给出采药时间限制。每株草药有各自的采摘耗时和价值要求辰辰在给定时间内采摘草药使总价值达到最大。本质上是一个 0 - 1 背包问题采药时间相当于背包容量草药的采摘耗时和价值分别对应物品的重量和价值需在时间限制内选择合适的草药物品以获取最大总价值。 这是最简单的背包模型的变种解题模版如下 由于第i行的状态只和第i-1行有关所以可以用滚动数组进行优化 习题1 分析
给定一个容量为\(V\)的箱子以及\(n\)个具有各自体积正整数的物品。目标是从这\(n\)个物品中选取若干个装入箱子使得箱子剩余的空间最小。这等价于在箱子容量限制下尽可能多地装入物品体积即最大化已装入物品的总体积类似于 0 - 1 背包问题中在背包容量限制下最大化物品总价值只不过这里的 “价值” 体现为物品体积。通过合理选择物品的组合来实现对箱子空间的最优利用需要运用算法策略如动态规划等求解。
这是一个背包问题的变种要求我们去求出最小的剩余的空间本质不就是求出能够得到的最大的体积吗所以这里的价值就是体积。我们的f[i][j]还是表示的前i个物品体积不超过j所能获得的最大的价值答案就是v-f[n][v]利用滚动数组来优化一下空间答案就是v-f[v]
伪代码如下 习题2二维0-1背包 分析 这是一个二维0-1背包问题我们纪要去关注皮卡丘的体力也要去关注精灵球的数量所以有两个花费我们的关注的子问题就是f[i][j][k]即只抓前i个小精灵花费不超过j个精灵球体力消费不超过k所能抓住的最多的小精灵数量。
因为还要求花费最少的体力所以我们要找到最小的k使得f[N][M][k]f[N][M][K]
使用滚动数组可以优化第一维
伪代码
习题3求方案数 分析
我们的子问题f[i][j]表示的是前i个数组成数j的方案数
这是一个求方案数的0-1问题特殊的点是初始化的时候我们对f[0][0]的初始化为1f[0][j],(j!0)为0.
状态转移方程是f[i][j]f[i-1][j]f[i-1][j-c[i]]不选第i个数组成j的方案数 选择第i个数组成j的方案数
伪代码如下 习题4求具体方案 分析
这是一道典型的 0 - 1 背包问题拓展题目。给定 (N) 件物品和一个容量为 (V) 的背包每件物品仅能使用一次第 (i) 件物品具有体积(v_i) 和价值 (w_i) 两个属性。
需找出将哪些物品装入背包能使物品总体积不超背包容量 \(V\) 的同时总价值达到最大。并且在满足总价值最大的众多方案中要输出所选物品编号构成序列的字典序最小的方案。
相比普通 0 - 1 背包问题仅需计算最大价值本题额外增加了输出字典序最小方案的要求这使得解题过程不仅要考虑价值最优还需在回溯确定选取物品时按照字典序规则来选择方案。
我们要根据我们自己的转移方程来确定转移的方向
伪代码
