蛮力法、动态规划法 求解01背包问题

动态规划法求01背包问题思路状态表⽰:f[i][j]表⽰前i个物品在容量为j的背包下的最⼤价值v[i]表⽰第i个物品的价值,w[i]表⽰第i个物品的重量状态转换:对于第i个物品如果当前背包不可以装下这个物品,那么当前的f[i][j] = f[i - 1][j],也就是上⼀个状态的最⼤价值如果当前背包可以装下这个物品,那么当前的f[i][j] = f[i - 1][j - v[i]] + w[i]和f[i - 1][j]取较⼤的那⼀个,第⼀个是考虑把第i个物品装⼊背包,那么背包物品的价值就是前i-1个物品装⼊容量为j-w[i]再加上第i个物品v[i]的价值,第⼆个是不把当前物品装⼊背包的价值,两个取⼤的那⼀个作为最优解代码详解：1. 0/1背包问题#include<iostream>using namespace std;const int N = 1e3 + 10;int f[N], w[N], v[N];int main(){int n, c;cin >> n >> c;for(int i = 1; i <= n; i ++ )cin >> v[i] >> w[i];for(int i = 1; i <= n; i ++)for(int j = c; j >= 0 && j >= v[i]; j --)f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[c] << endl;return 0;}}完全背包问题（每个物品可以使⽤⽆数次f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])完全背包问题本来应该是在背包问题上再加⼀个循环的，但是可以推导出下⾯这个样⼦f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])为什么呢，只是把0/1背包问题的f[i - 1][j - v[i] + w[i])的i-1换成了i就可以了？从头来说：完全背包问题，对于第i个物品，假设剩下的背包容量还可以装n个这个物品，那么⼀共就有n+1中决策⽅案，还有⼀种⽅案就是⼀个都不选那么对于第i个物品:它的最⼤价值就是f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]), f[i - 1][j - 2 * v[i]] + 2 * w[i]....)⼀直到n为⽌（①式）令 j = j - v[i] 那么f[i][j - v[i]] = max(f[i - 1][j - v[i]], f[i - 1][j - 2 * v[i]] + w[i].....)（②式）然后发现⼆式中的右边⽐较像⼀式中的第⼆项到最后⼀项，就是每⼀项都少了⼀个w[i]把⼆式带⼊⼀式，那么⼀式就是 f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]), 就是下⾯这个状态⽅程啦 ;#include<iostream>using namespace std;const int N = 1e3 + 10;int f[N][N], w[N], v[N];int main(){int n, c;cin >> n >> c;for(int i = 1; i <= n; i ++)cin >> v[i] >> w[i];for(int i = 1; i <= n; i ++ ){for(int j = 1; j <= c; j ++ ){f[i][j] = f[i - 1][j];if(j >= v[i])f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);}}cout << f[n][c] << endl;return 0;}完全背包优化：#include<iostream>using namespace std;const int N = 1e3 + 10;int f[N], w[N], v[N];int main(){int n, c;cin >> n >> c;for(int i = 1; i <= n; i ++)cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++ )for(int j = v[i]; j <= c; j ++ )//从前往后更新 f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[c] << endl;return 0;}。

动态规划——01背包问题01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。

01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }f[i,j]表示在前i件物品中选择若干件放在承重为j 的背包中，可以取得的最大价值。

Pi表示第i件物品的价值。

决策：为了背包中物品总价值最大化，第i件物品应该放入背包中吗？题目描述：有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。

首先要明确这张表是至底向上，从左到右生成的。

为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e 时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。

对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。

同理，c2=0，b2=3,a2=6。

对于承重为8的背包，a8=15,是怎么得出的呢？根据01背包的状态转换方程，需要考察两个值，一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi；在这里， f[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值f[i-1,j-Wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值f[i-1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a应该放入承重为8的背包以下是actionscript3 的代码[java]view plain copy1.public function get01PackageAnswer(bagItems:Array,bagSize:int):Array2.{3. var bagMatrix:Array=[];4. var i:int;5. var item:PackageItem;6.for(i=0;i<bagItems.length;i++)7. {8. bagMatrix[i] = [0];9. }10.for(i=1;i<=bagSize;i++)11. {12.for(var j:int=0;j<bagItems.length;j++)13. {14. item = bagItems[j] as PackageItem;15.if(item.weight > i)16. {17.//i背包转不下item18.if(j==0)19. {20. bagMatrix[j][i] = 0;21. }22.else23. {24. bagMatrix[j][i]=bagMatrix[j-1][i];25. }26. }27.else28. {29.//将item装入背包后的价值总和30. var itemInBag:int;31.if(j==0)32. {33. bagMatrix[j][i] = item.value;34.continue;35. }36.else37. {38. itemInBag = bagMatrix[j-1][i-item.weight]+item.value;39. }40. bagMatrix[j][i] = (bagMatrix[j-1][i] > itemInBag ? bagMatrix[j-1][i] : itemInBag)41. }42. }43. }44.//find answer45. var answers:Array=[];46. var curSize:int = bagSize;47.for(i=bagItems.length-1;i>=0;i--)48. {49. item = bagItems[i] as PackageItem;50.if(curSize==0)51. {52.break;53. }54.if(i==0 && curSize > 0)55. {56. answers.push();57.break;58. }59.if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight]==item.value)60. {61. answers.push();62. curSize -= item.weight;63. }64. }65.return answers;66.}PackageItem类[java]view plain copy1.public class PackageItem2.{3.public var name:String;4.public var weight:int;5.public var value:int;6.public function PackageItem(name:String,weight:int,value:int)7. { = name;9.this.weight = weight;10.this.value = value;11. }12.}测试代码[java]view plain copy1.var nameArr:Array=['a','b','c','d','e'];2.var weightArr:Array=[2,2,6,5,4];3.var valueArr:Array=[6,3,5,4,6];4.var bagItems:Array=[];5.for(var i:int=0;i<nameArr.length;i++)6.{7. var bagItem:PackageItem = new PackageItem(nameArr[i],weightArr[i],valueArr[i]);8. bagItems[i]=bagItem;9.}10.var arr:Array = ac.get01PackageAnswer(bagItems,10);出师表两汉：诸葛亮先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。

0/1背包问题1. 问题描述给定一个载重量为m，n个物品，其重量为w i，价值为v i，1<=i<=n，要求:把物品装入背包，并使包内物品价值最大2. 问题分析在0/1背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。

循环变量i，j意义：前i个物品能够装入载重量为j的背包中(n+1)*(m+1)数组value意义：value[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值若w[i]>j，第i个物品不装入背包否则，若w[i]<=j且第i个物品装入背包后的价值>value[i-1][j]，则记录当前最大价值（替换为第i个物品装入背包后的价值）计算最大价值的动态规划算法如下：//计算for(i=1;i<row;i++){for(j=1;j<col;j++){//w[i]>j,第i个物品不装入背包value[i][j]=value[i-1][j];//w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值int temp=value[i-1][j-w[i]]+v[i];if(w[i]<=j && temp>value[i][j])value[i][j]=temp;}}即该段程序完成以下n个阶段：1：只装入1个物品，确定在各种不同载重量的背包下，能够得到的最大价值2：装入2个物品，确定在各种不同载重量的背包下，能够得到的最大价值。

n：以此类推，装入n个物品，确定在各种不同载重量的背包下，能够得到的最大价值3. 问题求解确定装入背包的具体物品，从value[n][m]向前逆推：若value[n][m]>value[n-1][m]，则第n个物品被装入背包，且前n-1个物品被装入载重量为m-w[n]的背包中否则，第n个物品没有装入背包，且前n-1个物品被装入载重量为m的背包中以此类推，直到确定第一个物品是否被装入背包为止。

实验项目三 用蛮力法、动态规划法和贪心法求解0/1背包问题实验目的1、学会背包的数据结构的设计，针对不同的问题涉及到的对象的数据结构的设计也不同；2、对0-1背包问题的算法设计策略对比与分析。

实验内容：0/1背包问题是给定n 个重量为{w 1, w 2, … ,wn }、价值为{v 1, v 2, … ,vn }的物品和一个容量为C 的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。

在0/1背包问题中，物品i 或者被装入背包，或者不被装入背包，设xi 表示物品i 装入背包的情况，则当xi =0时，表示物品i 没有被装入背包，xi =1时，表示物品i 被装入背包。

根据问题的要求，有如下约束条件和目标函数：于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X =(x 1, x 2, …, xn )。

背包的数据结构的设计：typedef struct object{int n;//物品的编号int w;//物品的重量int v;//物品的价值}wup;wup wp[N];//物品的数组，N 为物品的个数int c;//背包的总重量1、蛮力法蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。

蛮力法的关键是依次处理所有的元素。

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

所以蛮力法解0/1背包问题的关键是如何求n 个物品集合的所有子集，n 个物品的子集有2的n 次方个，用一个2的n 次方行n 列的数组保存生成的子集，以下是生成子集的算法：⎪⎩⎪⎨⎧≤≤∈≤∑=)1(}1,0{1n i x C x w i n i i i （式1）∑=ni i i x v 1max （式2）void force(int a[16][4])//蛮力法产生4个物品的子集{int i,j;int n=16;int m,t;for(i=0;i<16;i++){ t=i;for(j=3;j>=0;j--){m=t%2;a[i][j]=m;t=t/2;}}for(i=0;i<16;i++)//输出保存子集的二维数组{for(j=0;j<4;j++){printf("%d ",a[i][j]);}printf("\n");}｝以下要依次判断每个子集的可行性，找出可行解:void panduan(int a[][4],int cw[])////判断每个子集的可行性，如果可行则计算其价值存入数组cw,不可行则存入0{int i,j;int n=16;int sw,sv;for(i=0;i<16;i++){sw=0;sv=0;for(j=0;j<4;j++){sw=sw+wp[j].w*a[i][j];sv=sv+wp[j].v*a[i][j];}if(sw<=c)cw[i]=sv;elsecw[i]=0;}在可行解中找出最优解，即找出可行解中满足目标函数的最优解。

用动态规划法求解0/1背包问题实验目的：1、掌握动态规划算法求解问题的一般特征和步骤。

2、使用动态规划法编程，求解0/1背包问题。

实验要求：1、掌握动态规划算法求解问题的一般特征和步骤。

2、使用动态规划法编程，求解0/1背包问题。

实验内容：1、问题描述：给定n种物品和一个背包，物品I的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？2、算法描述。

3、程序实现给出实例测试结果。

程序清单：#include<iostream>#include<iomanip>using namespace std;int c[50][50];int w[10],v[10];int x[10];int n;void KNAPSACK_DP(int n,int W){for(int k=0;k<=W;k++)c[0][k]=0;for(int i=1;i<=n;i++){c[i][0]=0;for(int k=1;k<=W;k++){if(w[i]<=k){if(v[i]+c[i-1][k-w[i]]>c[i-1][k])c[i][k]=v[i]+c[i-1][k-w[i]];elsec[i][k]=c[i-1][k];}elsec[i][k]=c[i-1][k];}}}void OUTPUT_SACK(int c[50][50],int k) {for(int i=n;i>=2;i--){if(c[i][k]==c[i-1][k])x[i]=0;else{x[i]=1;k=k-w[i];}}x[1]=(c[1][k]?1:0);for(int i=1;i<=n;i++)cout<<setw(4)<<x[i];}void main(){int m;cout<<"输入物品个数:";cin>>n;cout<<"依次输入物品的重量:"<<endl; for(int i=1;i<=n;i++)cin>>w[i];cout<<"依次输入物品的价值:"<<endl; for(int i=1;i<=n;i++)cin>>v[i];cout<<"输入背包最大容量:";cin>>m;for(int i=1;i<=m;i++)cout<<setw(4)<<i;cout<<endl;KNAPSACK_DP(n,m);cout<<"构造最优解过程如下:"<<endl; for(int j=1;j<=5;j++){for(int k=1;k<=m;k++)cout<<setw(4)<<c[j][k];cout<<endl;}cout<<"最优解为:"<<endl;OUTPUT_SACK(c,m);}运行结果：输入物品个数:5依次输入物品的重量:3 4 7 8 9依次输入物品的价值:4 5 10 11 13输入背包最大容量:171 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 构造最优解过程如下:0 0 4 4 4 4 4 4 4 4 4 4 4 4 4 4 40 0 4 5 5 5 9 9 9 9 9 9 9 9 9 9 90 0 4 5 5 5 10 10 10 14 15 15 15 19 19 19 19 0 0 4 5 5 5 10 11 11 14 15 16 16 19 21 21 21 0 0 4 5 5 5 10 11 13 14 15 17 18 19 21 23 24 最优解为:0 0 0 1 1实验体会：通过该实验，使用动态规划法编程，求解0/1背包问题，掌握动态规划算法求解问题的一般特征和步骤。

#动态规划0-1背包问题思路概述01背包问题是动态规划中的经典问题。

本篇⽂章主题：分析与优化最基本的01背包问题，对此类问题解题有⼀个基本的解题模板。

问题概述：有⼀个背包，他的容量为C（Capacity）。

现在有n种不同的物品编号分别为0、1....n-1。

其中每⼀件物品的重量为w(i)，价值为v(i)。

问可以向这个背包中放⼊哪些物品，使得在不超过背包容量的基础上，背包内物品价值最⼤。

思路：1.暴⼒法。

每⼀件物品都可以放进背包，也可以不放进背包。

找出所有可能组合⼀共2^n种组合时间复杂度：O((2^n)*n)2.动态规划法。

我们⾸先使⽤递归函数⾃上⽽下进⾏思考。

明确两点：第⼀、递归函数的定义第⼆、数据结构函数定义：F（n,C）递归函数定义：将n个物品放⼊容量为C的背包，使得价值最⼤。

这⾥要注意⼀下，第⼆个参数⼀定是剩余容量。

我们通过使⽤剩余容量来控制价值。

F（i，c） = F（i-1,c） = v(i) + F(i-1 , c-w(i))状态转移⽅程：F（i，c） = max( F(i-1 , c) , v(i) + F(i-1 , c-w(i) ) )即，当前价值的最⼤值为，不放⼊第i个物品(对应剩余容量为c)和放⼊第i个物品（对应剩余容量为C-w(i)）两种情况的最⼤值。

数据结构：借某盗版视频中的⼀个例⼦：我们这⾥选择⼀个⼆维数组，来迭代记录处理的结果。

这个⼆维数组dp[n][C] 其中n为物品数量，C为最⼤容量。

储存的值dp[i][j]含义为：考虑放⼊0~i 这些物品，背包容量为j我们考虑放⼊第⼀个物品。

由于第⼀个物品，编号为0，重量为1，价值为2。

对于容量为0的背包，放不下该物品，所以该背包价值为0.其余容量1~5，均可放下该物品。

所以只考虑物品0，不同背包⼤⼩对应的最⼤可能价值如图。

第⼀⾏处理为初始化，从第⼆⾏开始进⾏迭代。

第⼆⾏开始，就需要单独处理。

考虑dp[1][0]，背包容量为0，理所应当为0考虑dp[1][1]，此处我们依旧⽆法放⼊物品1，所以我们使⽤上⼀层的结果，即0~0物品在容量为1背包情况的最⼤价值。

一、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。

注：0/1背包问题：给定n 种物品和一个容量为C 的背包，物品i 的重量是i w ，其价值为i v ，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。

其中，每种物品只有全部装入背包或不装入背包两种选择。

二、所用算法的基本思想及复杂度分析：1.蛮力法求解0/1背包问题：1）基本思想：对于有n 种可选物品的0/1背包问题，其解空间由长度为n 的0-1向量组成,可用子集数表示。

在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。

2）代码:#include<iostream>#include<algorithm>using namespace std;#define N 100 //最多可能物体数struct goods //物品结构体{int sign; //物品序号int w; //物品重量int p; //物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w);}int max(int a,int b){return a<b?b:a;}int n,C,bestP=0,cp=0,cw=0;int X[N],cx[N];/*蛮力法求解0/1背包问题*/int Force(int i){if(i>n-1){if(bestP<cp&&cw+a[i].w<=C){for (int k=0;k<n;k++) X[k]=cx[k];//存储最优路径 bestP=cp;}return bestP;}cw=cw+a[i].w;cp=cp+a[i].p;cx[i]=1; //装入背包Force(i+1);cw=cw-a[i].w;cp=cp-a[i].p;cx[i]=0; //不装入背包Force(i+1);return bestP;}int KnapSack1(int n,goods a[],int C,int x[]){Force(0);return bestP;}int main(){goods b[N];printf("物品种数n: ");scanf("%d",&n); //输入物品种数printf("背包容量C: ");scanf("%d",&C); //输入背包容量for (int i=0;i<n;i++) //输入物品i 的重量w 及其价值v {printf("物品%d 的重量w[%d]及其价值v[%d]: ",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];}int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题 printf("蛮力法求解0/1背包问题:\nX=[ ");for(i=0;i<n;i++)cout<<X[i]<<" ";//输出所求X[n]矩阵printf("] 装入总价值%d\n",sum1);bestP=0,cp=0,cw=0;//恢复初始化}3）复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：)2()(n O n T 。