算法合集之《浅谈几类背包题》

各种类型的背包问题P01: 01背包问题 题⽬ 有N件物品和⼀个容量为V的背包。

第i件物品的费⽤是c，价值是w。

求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。

基本思路 这是最基础的背包问题，特点是：每种物品仅有⼀件，可以选择放或不放。

⽤⼦问题定义状态：即f[v]表⽰前i件物品恰放⼊⼀个容量为v的背包可以获得的最⼤价值。

则其状态转移⽅程便是：f[v]=max{f[v],f[v-c]+w}。

这个⽅程⾮常重要，基本上所有跟背包相关的问题的⽅程都是由它衍⽣出来的。

所以有必要将它详细解释⼀下：“将前i件物品放⼊容量为v的背包中”这个⼦问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为⼀个只牵扯前i-1件物品的问题。

如果不放第i件物品，那么问题就转化为“前i-1件物品放⼊容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放⼊剩下的容量为v-c的背包中”，此时能获得的最⼤价值就是f [v-c]再加上通过放⼊第i件物品获得的价值w。

注意f[v]有意义当且仅当存在⼀个前i件物品的⼦集，其费⽤总和为v。

所以按照这个⽅程递推完毕后，最终的答案并不⼀定是f[N] [V]，⽽是f[N][0..V]的最⼤值。

如果将状态的定义中的“恰”字去掉，在转移⽅程中就要再加⼊⼀项f[v-1]，这样就可以保证f[N] [V]就是最后的答案。

⾄于为什么这样就可以，由你⾃⼰来体会了。

优化空间复杂度 以上⽅法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。

先考虑上⾯讲的基本思路如何实现，肯定是有⼀个主循环i=1..N，每次算出来⼆维数组f[0..V]的所有值。

那么，如果只⽤⼀个数组f [0..V]，能不能保证第i次循环结束后f[v]中表⽰的就是我们定义的状态f[v]呢？f[v]是由f[v]和f [v-c]两个⼦问题递推⽽来，能否保证在推f[v]时（也即在第i次主循环中推f[v]时）能够得到f[v]和f[v -c]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c]保存的是状态f[v-c]的值。

背包问题全类型背包问题给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。

背包问题⼤体都可以⽤上述⽅式进⾏描述，但在具体的问题上有了不同的限制条件，于是便有了各种类型的背包问题。

背包问题可基本分为0-1背包问题、部分背包问题、多重背包问题、完全背包问题四⼤类。

接下从四种问题的解决的核⼼算法可以把部分背包问题单独化为⼀类，其核⼼算法为贪⼼。

其余的三种背包问题都可以⽤动态规划解决。

造成部分背包问题与其他的背包问题最⼤不同的原因是其限定条件的不同，部分1. 部分背包问题限定条件：每件物品可以只选取⼀部分完整问题描述：有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且每件物品可以进⾏分割，分割后的价值按取⾛重量占该物品总重量的⽐值计算。

在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法：贪⼼分析：根据本题的特殊性，我们可以任意地对某⼀部品进⾏分割，所以我们优先选择性价⽐⾼的物品，即单位重量下物品的价值。

解题代码//C++#include<cstdio>#include<algorithm>#include<iostream>using namespace std;struct bag { int w,v; //w表⽰重量 v表⽰价值 double p; //⽤来储存v/w 性价⽐}a[10005];bool cmp(bag x,bag y) { return x.p > y.p; //性价⽐⾼的物品排在前⾯}int main() {剩余 } } printf('%.2f\n', ans); //输出答案 return 0;}注意计算时注意数据类型在计算“性价⽐”的时候要注意，在C/C++等⼀部分语⾔中存在以下机制 int/int = int ，这样是⽆法计算出⼩数的，需要将其中任意⼀项浮点化即可。

一个最优解：w i X i Wi2w1X1nmaX v i X i 。

如果不是的话，设(y2,y3, , y n) 是这X i {0,1}( 2 i n) i2问题描述0/1 背包问题 :现有n种物品，对1<=i<=n ，已知第i种物品的重量为正整数 W i，价值为正整数 V i, 背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过 W 且总价值尽量大。

(注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分)算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：n w i x i Wi 1i i(1)x i { 0,1}( 1 i n)nmax v i x i (2)i1于是，问题就归结为寻找一个满足约束条件( 1 )，并使目标函数式( 2 )达到最大的解向量X (x1, x2 ,x3, ......... , x n) 。

首先说明一下 0-1 背包问题拥有最优解。

假设(X i,X2,X3,……，Xn)是所给的问题的一个最优解，则(X2,X3,……，Xn)是下面问题的n n n个问题的一个最优解，则v i y i v i X i ，且w1X1 w i y i W 。

因此，i 2 i 2 i 2n n n物品1W2=3V2=12物品2W3=4V3=40物品3W4=5V4=25物品4V1X1 V i y i V1X1 V i V i X i，这说明(X i,y2,y3, ............................................................... ,y n)是所给的 0-1 背包问i 2 i 2 i 1题比(X i,X2,X3, ........................... , X n)更优的解，从而与假设矛盾。

穷举法：用穷举法解决0-1背包问题，需要考虑给定 n个物品集合的所有子集，找出所有可能的子集(总重量不超过背包重量的子集) ，计算每个子集的总重量，然后在他们中找到价值最大的子集。

交通大学数理与软件工程学院题目0-1背包问题算法实现院系数理院专业班级信计09学生雷雪艳学号202105130指导教师二Ｏ一二年六月五日一、问题描述：1、0—1背包问题：给定n 种物品和一个背包，背包最大容量为M ，物品i 的重量是w i ,其价值是平P i ，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大？ 背包问题的数学描述如下：2、要求找到一个n 元向量(x1，x2…xn)，在满足约束条件：⎪⎩⎪⎨⎧≤≤≤∑10i i i x M w x 情况下，使得目标函数px ii ∑max ，其中，1≤i ≤n ；M>0；wi>0；pi>0。

满足约束条件的任何向量都是一个可行解，而使得目标函数到达最大的那个可行解那么为最优解[1]。

给定n 种物品和1个背包。

物品i 的重量是wi ，其价值为pi ，背包的容量为M 。

问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i 只有两种选择，即装入背包、不装入背包。

不能将物品i 装人背包屡次，也不能只装入局部的物品i 。

该问题称为0-1背包问题。

0-1背包问题的符号化表示是，给定M>0， w i >0， pi >0，1≤i ≤n ，要求找到一个n 元0-1向量向量(x1，x2…xn)， X i =0 或1 , 1≤i ≤n, 使得Mwx ii≤∑ ，而且px ii∑到达最大[2]。

二、解决方案：方案一：贪心算法1、贪心算法的根本原理与分析贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对围相当广的许多问题它能产生整体最优解。

在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。

贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子构造性质。

01背包问题：1.递归思想0- 1 背包问题如果采用递归算法来描述则非常清楚明白, 它的算法根本思想是假设用布尔函数knap( s, n) 表示n 件物品放入可容质量为s 的背包中是否有解( 当knap 函数的值为真时说明问题有解,其值为假时无解) . 我们可以通过输入s 和n 的值, 根据它们的值可分为以下几种情况讨论:( 1) 当s= 0时可知问题有解, 即函数knap( s, n) 的值为true; ( 2) 当s< 0 时这时不可能,所以函数值为false; ( 3) 当输入的s> 0 且n< 1 时即总物品的件数不足1, 这时函数值为false,只有s> 0 且n \1 时才符合实际情况,这时又分为两种情况: ( 1) 选择的一组物体中不包括Wn则knap( s, n) 的解就是knap( s, n- 1) 的解. ( 2) 选择的一组物体中包括Wn 则knap( s, n) 的解就是knap( s- Wn, n- 1) 的解. 这样一组Wn 的值就是问题的最佳解. 这样就将规模为n 的问题转化为规模为n- 1 的问题. 综上所述0- 1 背包问题的递归函数定义为:knap( s, n) =∕true, s= 0︳false, s< 0︳false, s> 0 且n< 1\knap( s, n- 1) 或knap( s- Wn, n- 1) , s> 0 且n>= 1采用此法求解0- 1 背包问题的时间复杂度为O( n) . 上述算法对于所有物品中的某几件恰能装满背包时能准确求出最佳解. 但一般情况是对于某一些物品无论怎么装都不能装满背包, 必须要按背包的最大容量来装. 如物品件数为4, 其质量分别为: 10, 2, 5, 4, 背包的容量为20, 则这四件物品无论怎么放都不能恰好装满背包, 但应能最大限度装, 即必须装下10, 5, 4 这三件物品, 这样就能得到最大质量19. 对于这种装不满的背包它的解决办法是这样的: 按所有物品的组合质量最大的方法装背包, 如果还装不满,则我们可以考虑剩余空间能否装下所有物品中最小的那件, 如果连最小的都装不下了则说明这样得到的解是最佳解, 问题解决. 这样我们必须先找出所有n 件物品中质量最小的那件( 它的质量为Min) , 但是为了问题的解决我们不能增加运算次数太多, 并且必须运用上述递归函数. 那么我们可通过修改s 的值即背包的容量, 从背包容量s 中减去k( 它的值是从0 到Min- 1 之间的一个整数值) , 再调用递归函数. 当k= 0 时即能装满背包, 其它值也能保证背包能最大限度装满, 这样所有问题都解决了.①例题一：简单背包问题Time Limit: 1000MS Memory Limit: 65535KBSubmissions: 2217 Accepted: 408Description设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。

背包问题解题⽅法总结最近在⽜客刷题遇到好⼏道背包问题，索性这两天集中⽕⼒刷了⼀些这类的题。

这⾥总结⼀下0-1背包、完全背包和多重背包三种基本的背包问题的解题套路。

(均基于动态规划的思想)0-1背包题⽬：有 N 件物品和容量为 W 的背包。

第 i 件物品的重量为 w_i，价值为 v_i，求将不超过背包容量的物品装⼊背包能得到的最⼤价值。

特点，每件物品的数量只有⼀个，可以选择放或不放某件物品。

⽤dp[i][j]表⽰将前 i+1 件总重量不超过 j 的物品放⼊背包能获得的最⼤价值，则可以⽤以下的转移⽅程来表⽰这个过程：\[dp[i,j] = max(dp[i - 1, j], dp[i-1, j-w[i]] + v[i]) \]注意到dp数组第i⾏的值更新只跟 i-1 ⾏有关，因此可以通过滚动数组或者反向更新的⽅式优化⼀下空间复杂度，在动态规划解题的时候这是⼀种常⽤的空间复杂度优化⽅式。

优化后的代码如下：for(int i = 0; i < N; i++){// 注意到这⾥dp需要从后往前更新，避免更新前就把旧值覆盖// 从实际意义上来说，因为每件物品只有⼀个，从后向前更新保证了更新是在还没放⼊过当前物品的前提下进⾏的for(int j = W; j >= w[i]; j--){dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);}}完全背包题⽬：有 N 种物品和容量为 W 的背包。

第 i 种物品的重量为 w_i，价值为 v_i，每种物品的数量⽆限。

求将不超过背包容量的物品装⼊背包能得到的最⼤价值。

特点：每种物品的数量⽆限多。

考虑到每种物品的数量⽆限。

⽤dp[j]表⽰在重量不超过 j 的情况下背包中物品可以达到的最⼤价值，则转移⽅程如下：\[dp[j]=max(dp[j], dp[j-w[i]]+v[i]) \]核⼼代码如下：for(int i = 0; i < N; i++){for(int j = w[i]; j <= W; j++){ // 这⾥和0-1背包不同dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);}}注意内层for循环是从前向后更新dp数组的，这是唯⼀和上⾯的0-1背包问题区别的地⽅。

浅谈几类背包题浙江省温州中学徐持衡指导老师：舒春平2008年12月目录摘要 (3)关键字 (3)正文 (4)一、引言 (4)二、背包的基本变换 (5)①完全背包 (5)②多次背包 (5)③单调队列优化☆ (6)三、其他几类背包问题 (8)①树形依赖背包（获取学分）☆ (8)②PKU3093☆ (11)四、总结 (12)附录 (13)参考文献 (13)文中原题 (13)摘要背包问题作为一个经典问题在动态规划中是很基础的一个部分，然而以0-1背包问题为原题，衍生转变出的各类题目，可以说是千变万化，当然解法也各有不同，如此就有了继续探究的价值。

本文就4道背包变化的题做一些探讨研究，提出本人的一些做法，希望能起到抛砖引玉的作用。

关键字动态规划背包优化正文一、引言背包问题是运筹学中的一个经典的优化难题，是一个NP-完全问题，但其有着广泛的实际应用背景，是从生活中一个常见的问题出发展开的：一个背包，和很多件物品，要在背包中放一些物品，以达到一定的目标。

在信息学中，把所有的数据都量化处理后，得到这样的一个问题：0-1 背包问题：给定n 件物品和一个背包。

物品i的价值是W i，其体积为V i，背包的容量为C。

可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。

在选择装入背包的物品时，对每件物品i ，要么装入背包，要么不装入背包。

不能将物品i 多次装入背包，也不能只装入部分物品i （分割物品i）。

因此，该问题称为0-1 背包问题。

用于求解0-1背包问题的方法主要有回溯算法、贪婪算法、遗传算法、禁忌搜索算法、模拟退火算法等。

在高中阶段，我们所谓的经典0-1背包问题，保证了所有量化后的数据均为正整数，即是一个特殊的整数规划问题，本文中如无特殊说明均以此为前提。

其经典的O(n*C)动规解法是：状态是在前i件物品中，选取若干件物品其体积总和不大于j，所能获得的最大价值为F i[j]，当前的决策是第i件物品放或者不放，最终得到转移方程：F i[j] = F i-1[j] (V i>j>=0)F i[j] = max{ F i-1[j] , F i-1[j-V i]+W i } (C>=j>=V i)其中由于F i只与F i-1有关，可以用滚动数组来节省程序的空间复杂度。

背包算法知识点总结背包问题是一种典型的组合优化问题，在计算机科学和运筹学中具有广泛的应用。

它的核心思想是在给定一组物品和背包容量的条件下，如何选择物品以使得背包中物品的总价值最大化。

背包问题可以分为0-1背包问题、完全背包问题和多重背包问题等类型。

0-1背包问题是最基本的背包问题，其中每个物品只有一件，且只能选择放入或不放入背包。

解决0-1背包问题通常采用动态规划的方法。

动态规划算法通过构建一个二维数组dp，其中dp[i][j]表示在前i个物品中，背包容量为j时的最大价值。

通过状态转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中w[i]和v[i]分别表示第i个物品的重量和价值，可以逐步填充dp数组，最终得到最优解。

完全背包问题与0-1背包问题的主要区别在于，完全背包问题中的物品可以无限选取。

这意味着对于每个物品，可以选择放入0个、1个、2个，甚至更多个。

解决完全背包问题同样可以采用动态规划的方法，但状态转移方程有所不同。

对于完全背包问题，dp[i][j] =max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中如果j >= w[i]，则需要考虑所有可能的选取数量。

多重背包问题是0-1背包问题和完全背包问题的结合，其中每种物品有限定的数量。

解决多重背包问题需要对每种物品的数量进行遍历，然后采用0-1背包问题的动态规划方法来求解。

除了动态规划，背包问题还可以通过贪心算法、回溯算法等方法求解。

贪心算法通过每次选择当前价值最大的物品来构建解，但这种方法并不总是能够得到最优解。

回溯算法则通过搜索所有可能的解空间来寻找最优解，但时间复杂度较高。

在实际应用中，背包问题可以用于资源分配、投资组合优化、货物装载等问题。

通过合理的算法设计和优化，可以有效地解决这些实际问题，提高资源的利用效率。

总结来说，背包问题是一类重要的组合优化问题，通过动态规划等算法可以有效求解。

分治法基本思想：
在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。

字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

基本代码：
结果截图：
总结：
贪心法基本思想：
贪心法（Greedy algorithm），又称贪心算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

基本代码：
结果截图：
总结：
分支限界法基本思想：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

基本代码：
结果截图：
总结：。

算法背包问题的五种方法1. 动态规划背包问题是一种经典的组合优化问题，动态规划是解决背包问题的常用方法之一。

动态规划将问题分解为子问题，并利用已解决子问题的结果来求解更大规模的问题。

对于背包问题，动态规划算法的基本思想是创建一个二维数组dp，其中dp[i][j]表示在前i个物品中选择若干个物品放入容量为j的背包中所能获得的最大价值。

通过填表格的方式，从子问题逐步求解到原问题，最终得到最优解。

2. 贪心算法贪心算法是另一种解决背包问题的方法。

它的基本思想是每一步都选择当前看起来最好的选择，而不考虑之前的选择对后续步骤的影响。

在背包问题中，贪心算法通常是按照物品的价值密度（价值与重量的比值）进行排序，然后依次选择价值密度最高的物品放入背包，直到背包容量不足为止。

贪心算法的优势在于其简单性和高效性，但它并不一定能得到最优解。

3. 分支定界法分支定界法是一种通过搜索方式求解背包问题的方法。

它的基本思想是通过搜索可能的解空间，并根据当前搜索路径的特性进行剪枝操作，从而减少搜索的时间和空间复杂度。

在背包问题中，分支定界法通常根据当前节点的上界（通过松弛问题得到）与当前最优解进行比较，如果上界小于当前最优解，则该节点不再继续拓展，从而减少搜索空间的大小，提高求解效率。

4. 回溯算法回溯算法是一种通过不断试探和回退的方式求解背包问题的方法。

它的基本思想是从问题的初始状态开始，不断地尝试不同的决策，并根据约束条件判断该决策是否可行。

如果决策可行，则继续尝试下一步决策；如果不可行，则回退到上一步并尝试其他决策。

在背包问题中，回溯算法通过递归的方式依次尝试每个物品的放入与不放入两种选择，直到找到满足约束条件的解或者穷尽所有可能。

5. 近似算法近似算法是一种通过快速求解背包问题的“近似”解来减小计算复杂度的方法。

它的基本思想是用一种简单而快速的策略求解背包问题，并且能够保证求解结果的近似程度。

在背包问题中，常见的近似算法有贪心算法和启发式算法。

背包问题系列算法详解背包问题是一个关于最优解的经典问题。

通常被讨论的最多的，最经典的背包问题是0-1背包问题(0-1 Knapsack Problem)。

它是一切背包问题及相关背包问题的基础。

本篇博文将详细分析0-1背包问题，并给出0-1背包问题的几种解法，同时也对0-1背包问题的内涵进行延伸，丰富其外延至完全背包问题和多重背包问题，并给出背包问题的算法实现过程，希望对大家有帮助。

一、0-1背包问题有N件物品和一个容量为V的背包。

第i件物品（每个物品只有一件）的费用是c[i]，价值是w[i]。

求解将哪些物品装入背包可使价值总和最大。

（1）递归求解算法如下：#include "iostream"#define CAPACITY 10#define GOODSNUM 6using namespace std;int nVol[GOODSNUM];int nValue[GOODSNUM];int knapsack(int itemIndex,int vol);void main(){int i=0,j=0;while(i<GOODSNUM){cout<<"input the "<<i+1<<"th item(volume and value):";cin>>nVol[i]>>nValue[i];i++;}cout<<"The max value is: "<<knapsack(GOODSNUM,CAPACITY)<<endl;}int knapsack(int itemIndex,int vol){if (itemIndex==0||vol==0){return 0;}else if (vol>=nVol[itemIndex] &&knapsack(itemIndex-1,vol)<knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex ]){return knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex];}elsereturn knapsack(itemIndex-1,vol);}分析：递归求解，求解过程中的绝大部分变量存在重复求解的过程，算法的效率较低，有待改进；那怎么改进呢？最有效的是用数组保存每次计算的结果，不用重复计算，于是有二维数组求解。

背包问题常州一中林厚从背包问题是信息学奥赛中的经典问题。

背包问题可以分为0-1背包和部分背包两种类型，0-1背包还可以再分为有限背包和无限背包（完全背包）。

背包问题的求解涉及到贪心、递归、递推、动态规划、搜索等多种算法。

熟练掌握各种背包问题及其变形试题的解法，是信息学奥赛选手从入门走向提高的必经之路。

先简单归纳一下涉及到的这几种重要算法：1、贪心：贪心法可以归纳为“每步取优”。

假设你的程序要走1~n共n步，则你只要保证在第i步（i=1..n）时走出的这一步是最优的。

所以，贪心法不是穷举，而只是一种每步都取优的走法。

但由于目光短浅，不考虑整体和全局，所以“步步最优”并不能保证最后的结果最优。

比如经典的“两头取数”问题、“n个整数连接成最大数”问题、“删数”问题等。

2、递归：递归算法可以归纳为将问题“由大化小”。

也就是将一个大问题分解为若干个“性质相同”的子问题，求解的的过程，一般是通过“函数的递归调用”，不断将大问题逐步细化、直至元问题（边界情况），最后通过递归函数的自动返回得到问题的解。

递归算法的关键是递归函数的构造，它的效率往往比较低，原因在于大量的“冗余”计算。

比如经典的“斐波那挈数列”问题，在递归实现时效率极低，存在着大量的冗余计算，可以采用“记忆化”的方法优化。

3、递推：递推问题往往有一个“递推公式”，其实和“递归公式”差不多，但是出发点不一样，递归的思想是“要想求什么就要先求出什么”。

而递推是从问题的边界情况（初始状态）出发，一步步往下走，直到走完n步，判断最后的解。

由于其中的每一步并不知道当前一步的哪一个值对后面的步骤有用，所以只能把所有情况（一步的所有走法）全部计算出来，也造成了很多的“冗余计算”。

时间上往往没有太多的优化余地，但空间上经常利用“滚动数组”等方式，把空间复杂度由O（n2）降到O（2n）。

比如经典的“杨辉三角形”问题、“判断n是否是斐波那挈数”问题等。

4、动态规划：本质上是一种克服了“冗余”的“递归”算法。

【转载】各种背包问题模板讲解 背包问题集合 ⼀般来说，动态规划（DP）。

都是初学者最难闯过的⼀关，⽽在这⾥详细解说动态规划的⼀种经典题型：背包问题。

这⾥介绍的背包分为以下⼏种：01背包，完全背包，多重背包，混合背包，⼆维费⽤的背包。

（以后会持续更新）【⼀：01背包】⾸先放上例题：01背包问题【题⽬描述】：⼀个旅⾏者有⼀个最多能装M公⽄的背包，现在有n件物品，他们的重量分别是W1，W2…Wn，它们的价值分别是C1，C2……Cn，求旅⾏者能够获得的最⼤总价值。

【输⼊格式】：第⼀⾏：两个整数，M，（背包容量，M<=200）和N（物品数量N<=30）第2⾄N+1⾏，每⾏两个整数，Wi,Ci,表⽰每个物品的重量和价值。

【输出格式】：仅⼀⾏，⼀个数，表⽰最⼤总价值。

【输⼊样例#1】：10 42 13 34 57 9【输出样例#1】：1201背包问题可以说是最简单的背包问题，简单之处就在：他的每⼀个物品都只有⼀个。

⾸先定义⼀个f[MAXN][MAXN]数组，⽤来记录最⼤价值。

即：f[i][v]表⽰的就是当前i件物品放⼊⼀个容量为v的背包的时候可以获得的最⼤价值。

01背包的状态转移⽅程式便是：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])。

众所周知DP问题最重要的便是状态转移⽅程式了，那么这个状态转移⽅程式究竟是怎么来的呢？？详解来啦“既然说了是“将第i件物品放⼊背包”，那么如果只考虑第i件物品的⽅式策略，那么就只和第i-1件物品有关了，如果是放第i件物品，那么问题就转化为：“前i-1件物品放⼊容量为v的背包中”，此时能够获得的最⼤价值就是f[i-1][v-w[i]]，也就是第i-1件物品放⼊容量为v（原来的总容量）减去w[i]（第i件物品的占容）产⽣的最优价值，再加上放通过⼊第i件物品增加的价值c[i]。

那么放⼊第i件物品产⽣的最⼤价值就是要在”放“，或者是”不放“中选择了，”不放“的话，产⽣的价值就是f[i-1] [v]，”放“的话，产⽣的最⼤价值就是,f[i-1][v-w[i]]+c[i])。

背包问题的解决算法在日常生活中，我们常常会遇到背包问题。

比如说，你需要出门远足，但是又不想背太多的东西，怎么办？这时候，你就需要一种背包算法，用以帮助你选出最好的装备。

当然，背包算法不仅仅局限于这种场景，还可以应用于计算机科学等领域。

背包问题可以定义为：在限定容量下，找到能够装下最大价值物品的选择方案。

在计算机科学中，背包问题又分为0/1背包和无限背包两种类型。

0/1背包指的是在数量有限的情况下，每种物品只能选择一次；无限背包则意味着每种物品可以重复选择。

现在，我们来讨论一下几种常见的背包算法。

1. 贪心算法贪心算法是一种常见的解决背包问题的方法。

首先，根据每个物品的价值大小来求解。

然后，将每个物品按照其价值排序。

按照顺序，从价值最高的开始选择，在能够装下的情况下，尽量选择多的物品。

这种方法容易理解，但是它并不一定能够获得最优解。

2. 动态规划算法动态规划是解决背包问题最常用的算法。

它将问题分解成多个子问题，并且利用已经求解过的子问题来递推求解更大的问题。

具体来说，动态规划算法需要在每个状态中维护当前已经选择的物品，以及它们的价值和总重量。

然后，根据每个物品的价值，计算出在当前重量下选择这个物品的最大价值，同时比较这个价值和不选择这个物品的价值大小，最终得出最优解。

3. 回溯算法回溯算法也是一种解决背包问题的方法。

它的基本思想是，从初始状态开始，考虑每种可能的选择，最终找到最优解。

相比其他算法，回溯算法需要考虑所有可能的解，因此在问题较大的时候，它的时间复杂度可能较高。

但是，回溯算法通常能够得到最优解。

4. 分支定界算法分支定界算法也是一种解决背包问题的方法。

它通过确定每种物品能否被选择，来缩小解空间并加速搜索。

具体来说，它会根据价值和重量来对物品进行排序，并尝试从价值最高的物品开始选择。

然后，将剩余的物品按选择顺序进行排序，并对每个物品进行深度优先搜索，直到搜索到了可行解或者不可行解为止。

在实际应用中，以上几种算法都有其优缺点。

分组背包：Problem C: 超市购物Time Limit: 1 Sec Memory Limit: 128 MBSUBMIT: 21 Solved: 10[SUBMIT][STATUS]Description上次去超市扫荡回来的东西用完了,Staginner又得跑超市一趟，出发前他列了一张购物清单，打算去买K种不同的商品,每种买一件。

到了超市，Staginner发现每种商品有N个品牌，每个品牌此商品的价格为Vi，对Staginner的作用值为Wi，他会从这N个品牌里面挑一个品牌买。

这时，Staginner突然想起出门时只带了M元钱，又懒得去取钱了，所以不一定能买完K种商品，只好尽可能地让买的东西对自己的总作用值ans最大。

Input多组样例。

第一行两个整数K，M代表Staginner想买的不同种类商品的数目和他带的钱 (0 < K <= 30, 0 < M <= 2000)以下输入分为K个部分，代表K种商品。

每个部分第一行为一个数字N，代表第k种商品的N个品牌,N不大于10。

之后跟着N 行，每行两个数字，代表物品的价格Vi和作用值Wi。

其中 0 < Vi < M。

Output输出Case #: 最大总作用值，每两个样例之间有一个空行。

Sample Input3 100350 60020 70030 800230 50040 600160 2002 5002200 1000260 12001280 300Sample OutputCase 1: 1400Case 2: 1300HINT#include<stdio.h>#include<string.h>int bag[100][100],dp[2500],val[100][100];int main(){int k,m,n,i,j,t,cnt=0;while(scanf("%d %d",&t,&m)!=EOF){memset(dp,0,sizeof(dp));memset(val,0,sizeof(val));memset(bag,0,sizeof(bag));for(i=0;i<t;i++){scanf("%d",&n);bag[i][0]=n;for(j=1;j<=n;j++)scanf("%d %d",&bag[i][j],&val[i][j]);}for(i=0;i<t;i++)for(j=m;j>=0;j--)for(k=1;k<=bag[i][0];++k)if(bag[i][k]<=j)dp[j]=dp[j]>(dp[j-bag[i][k]]+val[i][k])?dp[j]:(dp[j-bag[i][k]]+val[i][k] );printf("Case %d: %d\n",++cnt,dp[m]);printf("\n");}return 0;}RobberiesTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3802 Accepted Submission(s): 1433Problem DescriptionThe aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.InputThe first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj .Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .OutputFor each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.Notes and Constraints0 < T <= 1000.0 <= P <= 1.00 < N <= 1000 < Mj <= 1000.0 <= Pj <= 1.0A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.Sample Input30.04 31 0.022 0.033 0.050.06 32 0.032 0.033 0.050.10 31 0.032 0.023 0.05Sample Output246题意：输入一个数表示一共多少组数据输入一个浮点型数表示小偷被抓的几率不超过这个情况下能偷的最多钱输入一个整形表示多少个银行输入3组数据一组2个数分别是该银行的钱以及被抓的几率求小偷不被抓的情况下能偷的最多钱思路：一开始我是让几率当背包然后钱做val 但是这样是错误的因为几率是浮点型虽然可以*100变成整形但是几率是相乘得出的而几率当背包无法模拟几率的相乘由题中数据看仿佛用几率当背包然后几率相加能得到样例中的结果但是这是错误的思想几率哪有加的啊所以就要变通一下把钱当背包看总共多少钱把几率当背包#include<stdio.h>#include<string.h>double val[105],x;int wei[105];double bag[10500000];void _01bag(int v,int m){int i,j;for(i=0;i<v+3;i++)bag[i]=0;bag[0]=1;for(i=0;i<m;i++)for(j=v;j>=wei[i];j--)if(bag[j]<bag[j-wei[i]]*(1-val[i]))bag[j]=bag[j-wei[i]]*(1-val[i]);for(i=v;i>=0;i--)if(bag[i]>=1-x) {printf("%d\n",i);break;}return;}int main(){int t,i,m,v;scanf("%d",&t);while(t--){v=0;scanf("%lf %d",&x,&m);for(i=0;i<m;i++){scanf("%d %lf",&wei[i],&val[i]);v=v+wei[i];}_01bag(v,m);}return 0;}I NEED A OFFER!Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8472 Accepted Submission(s): 3083Problem DescriptionSpeakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。