算法背包问题的五种方法

求解背包问题的一种新的近似算法引言：现实中有很多问题至今还没有多项式式时间可解的算法，如本文的背包问题。

实际应用中可以通过近似算法来获得一个解。

近似算法在理想情况下，可以保证近似解与最优解只有一个常数之差。

背包问题的近似算法现实中有很多问题至今还没有多项式式时间可解的算法，如本文的背包问题。

实际应用中可以通过近似算法来获得一个解。

近似算法在理想情况下，可以保证近似解与最优解只有一个常数之差。

近似算法设计的两个基本要求：算法能在N的多项式时间内完成算法的近似解满足一定的精度4.1 近似算法定义接下来我们来介绍几个定义，来衡量近似算法的性能。

定义1（近似比）设问题Π是最大化问题，I是问题Π的一个实例：A是问题Π的一个近似算法，A(I)是用算法对问题Π的实例I求解得到的近似值OPTA是问题Π的最优算法，OPTA(I)是算法OPTA对问题Π的实例I求解得到的准确值则可以定义近似算法A的近似比率ρ(I):ρ(I)=OPTA(I)A(I)最小化问题的近似比为：ρ(I)=A(I)OPTA(I)算法A的近似比率ρ(I)总是大于等于1，近似比率越小，算法越好。

定义2(相对误差界) 若对于输入规模为n的问题，存在一个函数ϵ(n)，使得：ρ(I)=|OPTA(I)−A(I)OPTA(I)|≤ϵ(n)近似算法的近似比率ρ(I)与相对误差的界ϵ(n)存在如下的关系：ϵ(n)=ρ(I)−1定义3（优化问题近似方案）把近似算法A的近似比满足如下条件：且{Aϵ|ϵ>0且ρ(I,ϵ)≤1+ϵ}称为优化问题的近似方案。

定义4（多项式近似方案，PAS）如果近似方案中的每一个算法Aϵ，以输入实例规模的多项式时间运行，则称该方案为多项式近似方案（Polynomial Approximiation Scheme ,PAS )定义5（完全多项式近似方案，FPAS）如果近似方案中的每一个算法Aϵ的计算时间是1ϵ和n的多项式，则称这个近似方案是完全多项式近似方案（Fully Polynomial Approximiation Scheme ,FPAS )完全多项式近似方案(FPAS)通俗理解，在理想情况下，若ϵ减少某个常数倍，近似方案中算法的计算时间的增长也不会超过某个常数倍。

贪⼼算法-01背包问题1、问题描述：给定n种物品和⼀背包。

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

问:应如何选择装⼊背包的物品，使得装⼊背包中物品的总价值最⼤?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找⼀n元向量(x1,x2,…,xn,), xi∈{0,1}, ∋ ∑ wi xi≤c,且∑ vi xi达最⼤.即⼀个特殊的整数规划问题。

2、最优性原理：设(y1,y2,…,yn)是 (3.4.1)的⼀个最优解.则(y2,…,yn)是下⾯相应⼦问题的⼀个最优解:证明:使⽤反证法。

若不然,设(z2,z3,…,zn)是上述⼦问题的⼀个最优解,⽽(y2,y3,…,yn)不是它的最优解。

显然有∑vizi > ∑viyi (i=2,…,n)且 w1y1+ ∑wizi<= c因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的⼀个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,⽭盾。

3、递推关系：设所给0-1背包问题的⼦问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。

由0-1背包问题的最优⼦结构性质，可以建⽴计算m(i，j)的递归式:注:(3.4.3)式此时背包容量为j，可选择物品为i。

此时在对xi作出决策之后,问题处于两种状态之⼀:(1)背包剩余容量是j,没产⽣任何效益；(2)剩余容量j-wi,效益值增长了vi ；使⽤递归C++代码如下：#include<iostream>using namespace std;const int N=3;const int W=50;int weights[N+1]={0,10,20,30};int values[N+1]={0,60,100,120};int V[N+1][W+1]={0};int knapsack(int i,int j){int value;if(V[i][j]<0){if(j<weights[i]){value=knapsack(i-1,j);}else{value=max(knapsack(i-1,j),values[i]+knapsack(i-1,j-weights[i]));}V[i][j]=value;}return V[i][j];}int main(){int i,j;for(i=1;i<=N;i++)for(j=1;j<=W;j++)V[i][j]=-1;cout<<knapsack(3,50)<<endl;cout<<endl;}不使⽤递归的C++代码：简单⼀点的修改//3d10-1 动态规划背包问题#include <iostream>using namespace std;const int N = 4;void Knapsack(int v[],int w[],int c,int n,int m[][10]);void Traceback(int m[][10],int w[],int c,int n,int x[]);int main(){int c=8;int v[]={0,2,1,4,3},w[]={0,1,4,2,3};//下标从1开始int x[N+1];int m[10][10];cout<<"待装物品重量分别为："<<endl;for(int i=1; i<=N; i++){cout<<w[i]<<" ";}cout<<endl;cout<<"待装物品价值分别为："<<endl;for(int i=1; i<=N; i++){cout<<v[i]<<" ";}cout<<endl;Knapsack(v,w,c,N,m);cout<<"背包能装的最⼤价值为："<<m[1][c]<<endl;Traceback(m,w,c,N,x);cout<<"背包装下的物品编号为："<<endl;for(int i=1; i<=N; i++){if(x[i]==1){cout<<i<<" ";}}cout<<endl;return 0;}void Knapsack(int v[],int w[],int c,int n,int m[][10]){int jMax = min(w[n]-1,c);//背包剩余容量上限范围[0~w[n]-1] for(int j=0; j<=jMax;j++){m[n][j]=0;}for(int j=w[n]; j<=c; j++)//限制范围[w[n]~c]{m[n][j] = v[n];}for(int i=n-1; i>1; i--){jMax = min(w[i]-1,c);for(int j=0; j<=jMax; j++)//背包不同剩余容量j<=jMax<c{m[i][j] = m[i+1][j];//没产⽣任何效益}for(int j=w[i]; j<=c; j++) //背包不同剩余容量j-wi >c{m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//效益值增长vi }}m[1][c] = m[2][c];if(c>=w[1]){m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);}}//x[]数组存储对应物品0-1向量,0不装⼊背包，1表⽰装⼊背包void Traceback(int m[][10],int w[],int c,int n,int x[]){for(int i=1; i<n; i++){if(m[i][c] == m[i+1][c]){x[i]=0;}else{x[i]=1;c-=w[i];}}x[n]=(m[n][c])?1:0;}运⾏结果：算法执⾏过程对m[][]填表及Traceback回溯过程如图所⽰：从m(i，j)的递归式容易看出，算法Knapsack需要O(nc)计算时间; Traceback需O(n)计算时间；算法总体需要O(nc)计算时间。

背包问题九讲 v1.0目录第一讲 01背包问题第二讲完全背包问题第三讲多重背包问题第四讲混合三种背包问题第五讲二维费用的背包问题第六讲分组的背包问题第七讲有依赖的背包问题第八讲泛化物品第九讲背包问题问法的变化附：USACO中的背包问题前言本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这个计划的内容是写作一份较为完善的NOIP难度的动态规划总结，名为《解动态规划题的基本思考方式》。

现在你看到的是这个写作计划最先发布的一部分。

背包问题是一个经典的动态规划模型。

它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题，我也将它放在我的写作计划的第一部分。

读本文最重要的是思考。

因为我的语言和写作方式向来不以易于理解为长，思路也偶有跳跃的地方，后面更有需要大量思考才能理解的比较抽象的内容。

更重要的是：不大量思考，绝对不可能学好动态规划这一信息学奥赛中最精致的部分。

你现在看到的是本文的1.0正式版。

我会长期维护这份文本，把大家的意见和建议融入其中，也会不断加入我在OI学习以及将来可能的ACM-ICPC的征程中得到的新的心得。

但目前本文还没有一个固定的发布页面，想了解本文是否有更新版本发布，可以在OIBH论坛中以“背包问题九讲”为关键字搜索贴子，每次比较重大的版本更新都会在这里发贴公布。

目录第一讲 01背包问题这是最基本的背包问题，每个物品最多只能放一次。

第二讲完全背包问题第二个基本的背包问题模型，每种物品可以放无限多次。

第三讲多重背包问题每种物品有一个固定的次数上限。

第四讲混合三种背包问题将前面三种简单的问题叠加成较复杂的问题。

第五讲二维费用的背包问题一个简单的常见扩展。

第六讲分组的背包问题一种题目类型，也是一个有用的模型。

后两节的基础。

第七讲有依赖的背包问题另一种给物品的选取加上限制的方法。

第八讲泛化物品我自己关于背包问题的思考成果，有一点抽象。

动态规划——01背包问题⼀、最基础的动态规划之⼀01背包问题是动态规划中最基础的问题之⼀，它的解法完美地体现了动态规划的思想和性质。

01背包问题最常见的问题形式是：给定n件物品的体积和价值，将他们尽可能地放⼊⼀个体积固定的背包，最⼤的价值可以是多少。

我们可以⽤费⽤c和价值v来描述⼀件物品，再设允许的最⼤花费为w。

只要n稍⼤，我们就不可能通过搜索来遍查所有组合的可能。

运⽤动态规划的思想，我们把原来的问题拆分为⼦问题，⼦问题再进⼀步拆分直⾄不可再分（初始值），随后从初始值开始，尽可能地求取每⼀个⼦问题的最优解，最终就能求得原问题的解。

由于不同的问题可能有相同的⼦问题，⼦问题存在⼤量重叠，我们需要额外的空间来存储已经求得的⼦问题的最优解。

这样，可以⼤幅度地降低时间复杂度。

有了这样的思想，我们来看01背包问题可以怎样拆分成⼦问题：要求解的问题是：在n件物品中最⼤花费为w能得到的最⼤价值。

显然，对于0 <= i <= n,0 <= j <= w，在前i件物品中最⼤花费为j能得到的最⼤价值。

可以使⽤数组dp[n + 1][w + 1]来存储所有的⼦问题，dp[i][j]就代表从前i件物品中选出总花费不超过j时的最⼤价值。

可知dp[0][j]值⼀定为零。

那么，该怎么递推求取所有⼦问题的解呢。

显⽽易见，要考虑在前i件物品中拿取，⾸先要考虑前i - 1件物品中拿取的最优情况。

当我们从第i - 1件物品递推到第i件时，我们就要考虑这件物品是拿，还是不拿，怎样收益最⼤。

①：⾸先，如果j < c[i]，那第i件物品是⽆论如何拿不了的，dp[i][j] = dp[i - 1][j];②：如果可以拿，那就要考虑拿了之后收益是否更⼤。

拿这件物品需要花费c[i]，除去这c[i]的⼦问题应该是dp[i - 1][j - c[i]]，这时，就要⽐较dp[i - 1][j]和dp[i - 1][j - c[i]] + v[i]，得出最优⽅案。

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

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

背包问题可基本分为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 ，这样是⽆法计算出⼩数的，需要将其中任意⼀项浮点化即可。

背包问题（3）：完全背包完全背包也是⼀种基本的背包问题模型，其基本特点是：每种物品可以放⽆限多次。

这个问题⾮常类似于0/1背包问题，所不同的是每种物品有⽆限件。

也就是从每种物品的⾓度考虑，与它相关的策略已并⾮取或不取两种，⽽是有取0件、取1件、取2件……等很多种。

完全背包问题的⼀般描述为：有N个物品，第i个物品的重量与价值分别为W[i]与P[i]。

背包容量为V，问在每个物品有⽆限个（物品必须保持完整）的情况下，如何让背包装⼊的物品具有更⼤的价值总和。

其⼀般解题思路为：令 f[i][j] 表⽰从编号1~i的物品中挑选任意数量的任意物品放⼊容量为j的背包中得到的最⼤价值，那么有f[i][j]=max { f[i−1][j]，f[i−1][j−k∗W[i]]+k∗P[i] } （0≤k && k∗W[i]≤j）编写代码时，可采⽤如下的循环。

for ( i=1;i<=N;i++) // 依次对每个物品进⾏处理for (j=1;j<=V;j++)for (k=1; k<=V/W[i];k++) // 物品最多只能放多少件{If (k*W[i]<=j)f[i][j]=max(f[i-1][j],f[i-1][j-k*W[i]]+k*P[i]);elsef[i][j]=f[i-1][j];}所求的最优值为f[N][V]。

同样完全背包也可以进⾏空间优化，将⼆维数组优化为⼀维数组，即f[j]=max { f[j]，f[j−k∗W[i]]+k∗P[i] } （0≤k && k∗W[i]≤j）编写代码时，⼀般采⽤如下的⼆重循环。

for (i=1;i<=N;i++) // 装⼊背包的物品个数为Nfor ( j=W[i];j<=V;j++) // 完全背包按由⼩到⼤顺序枚举重量f[j]=max(f[j],f[j-W[i]]+P[i]); // 状态转移所求的最优值为f[V]。

分⽀限界法解决01背包问题1. 问题描述设有n个物体和⼀个背包,物体i的重量为wi价值为pi ,背包的载荷为M, 若将物体i（1<= i <=n）装⼊背包,则有价值为pi . ⽬标是找到⼀个⽅案, 使得能放⼊背包的物体总价值最⾼.设N=3, W=(16,15,15), P=(45,25,25), C=30（背包容量）2. 队列式分⽀限界法可以通过画分⽀限界法状态空间树的搜索图来理解具体思想和流程每⼀层按顺序对应⼀个物品放⼊背包（1）还是不放⼊背包（0）步骤：①⽤⼀个队列存储活结点表，初始为空② A为当前扩展结点，其⼉⼦结点B和C均为可⾏结点，将其按从左到右顺序加⼊活结点队列，并舍弃A。

③按FIFO原则，下⼀扩展结点为B，其⼉⼦结点D不可⾏，舍弃；E可⾏，加⼊。

舍弃B④ C为当前扩展结点，⼉⼦结点F、G均为可⾏结点，加⼊活结点表，舍弃C⑤扩展结点E的⼉⼦结点J不可⾏⽽舍弃；K为可⾏的叶结点，是问题的⼀个可⾏解，价值为45⑥当前活结点队列的队⾸为F, ⼉⼦结点L、M为可⾏叶结点，价值为50、25⑦ G为最后⼀个扩展结点，⼉⼦结点N、O均为可⾏叶结点，其价值为25和0⑧活结点队列为空，算法结束，其最优值为50注：活结点就是不可再进⾏扩展的节点，也就是两个⼉⼦还没有全部⽣成的节点3. 优先队列式分⽀限界法3.1 以活结点价值为优先级准则步骤：①⽤⼀个极⼤堆表⽰活结点表的优先队列，其优先级定义为活结点所获得的价值。

初始为空。

②由A开始搜索解空间树，其⼉⼦结点B、C为可⾏结点，加⼊堆中，舍弃A。

③B获得价值45，C为0. B为堆中价值最⼤元素，并成为下⼀扩展结点。

④ B的⼉⼦结点D是不可⾏结点，舍弃。

E是可⾏结点，加⼊到堆中。

舍弃B。

⑤ E的价值为45，是堆中最⼤元素，为当前扩展结点。

⑥ E的⼉⼦J是不可⾏叶结点，舍弃。

K是可⾏叶结点，为问题的⼀个可⾏解价值为45。

⑦继续扩展堆中唯⼀活结点C，直⾄存储活结点的堆为空，算法结束。

c语言算法--贪婪算法---0/1背包问题在0 / 1背包问题中，需对容量为c 的背包进行装载。

从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。

对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ?i=1pi xi 取得最大值。

约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。

在这个表达式中，需求出xt 的值。

xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。

0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。

货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。

例1-8 在杂货店比赛中你获得了第一名，奖品是一车免费杂货。

店中有n 种不同的货物。

规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi 。

你的目标是使车中装载的物品价值最大。

当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。

这个问题可仿照0 / 1背包问题进行建模，其中车对应于背包，货物对应于物品。

0 / 1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。

在每一步过程中利用贪婪准则选择一个物品装入背包。

一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。

这种策略不能保证得到最优解。

例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。

当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。

而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。

另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。

背包问题：0-1背包、完全背包和多重背包背包问题泛指以下这⼀种问题：给定⼀组有固定价值和固定重量的物品，以及⼀个已知最⼤承重量的背包，求在不超过背包最⼤承重量的前提下，能放进背包⾥⾯的物品的最⼤总价值。

这⼀类问题是典型的使⽤动态规划解决的问题，我们可以把背包问题分成3种不同的⼦问题：0-1背包问题、完全背包和多重背包问题。

下⾯对这三种问题分别进⾏讨论。

1.0-1背包问题0-1背包问题是指每⼀种物品都只有⼀件，可以选择放或者不放。

现在假设有n件物品，背包承重为m。

对于这种问题，我们可以采⽤⼀个⼆维数组去解决：f[i][j]，其中i代表加⼊背包的是前i件物品，j表⽰背包的承重，f[i][j]表⽰当前状态下能放进背包⾥⾯的物品的最⼤总价值。

那么，f[n][m]就是我们的最终结果了。

采⽤动态规划，必须要知道初始状态和状态转移⽅程。

初始状态很容易就能知道，那么状态转移⽅程如何求呢？对于⼀件物品，我们有放进或者不放进背包两种选择：（1）假如我们放进背包，f[i][j] = f[i - 1][j - weight[i]] + value[i]，这⾥的f[i - 1][j - weight[i]] + value[i]应该这么理解：在没放这件物品之前的状态值加上要放进去这件物品的价值。

⽽对于f[i - 1][j - weight[i]]这部分，i - 1很容易理解，关键是 j - weight[i]这⾥，我们要明⽩：要把这件物品放进背包，就得在背包⾥⾯预留这⼀部分空间。

（2）假如我们不放进背包，f[i][j] = f[i - 1][j]，这个很容易理解。

因此，我们的状态转移⽅程就是：f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i])当然，还有⼀种特殊的情况，就是背包放不下当前这⼀件物品，这种情况下f[i][j] = f[i - 1][j]。