算法笔记动态规划01背包问题.docx

《算法笔记动态规划01背包问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、0019算法笔记——【动态规划】0-1背包问题     1、问题描述：    给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?    形式化描述：给定c>0,wi>0,vi>0,1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1},∋∑wixi≤c,且∑vixi达最大.即一个特殊的整数规划问题。       2、最优性原理：    设(y1,y2,…,yn)是(3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解:    证明:使用

2、反证法。若不然,设(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、不是背包问题的最优解,矛盾。       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 ；     算法具体代码如下：[cpp] viewplain copy1

4、.//3d10-1 动态规划 背包问题  2.#include "stdafx.h"  3.#include    4.using namespace std;   5.  6.const int N = 4;  7.  8.void Knapsack(int v[],int w[],int c,int n,int m[][10]);  9.void Traceback(int m[][10],int w[],int c,int n,int x[]);  10.  11.int main()  12.{  13.    int c=8; 

5、 14.    int v[]={0,2,1,4,3},w[]={0,1,4,2,3};//下标从1开始  15.    int x[N+1];  16.    int m[10][10];  17.  18.    cout<<"待装物品重量分别为："<

6、 for(int i=1; i<=N; i++)  27.    {  28.        cout<

7、    {  2.        if(x[i]==1)  3.        {  4.            cout<

8、j=0; j<=jMax;j++)  16.