背包问题--动态规划

背包问题

0-1背包问题涉及最值的获取，普通的测试方法很难得到结果，需要采动态规划方法。公式如下:

其中，c[i,w]表示在包含了i物品的情况下背包承重为w下背包的最大价值。如果物品i重量大于w，直接跳过；如果物品i重量小于w，分为两种情况：

（1）i物品装入，则要判断剩余i-1个物品在重量为w-wi前提下最大价值+i物品本身价值；

（2）i物品不装入，判断剩余i-1物品在质量为w下最大价值，这是解题的关键；

题目描述：

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

name	weight	value	1	2	3	4	5	6	7	8	9	10
a	2	6	0	6	6	9	9	12	12	15	15	15
b	2	3	0	3	3	6	6	9	9	9	10	11
c	6	5	0	0	0	6	6	6	6	6	10	11
d	5	4	0	0	0	6	6	6	6	6	10	10
e	4	6	0	0	0	6	6	6	6	6	6	6

表格生成过程是从下至上，从左到右的，d2含义：只有物品d时，有个承重为2的背包，那么这个背包的最大价值是0，因为d物品的重量是5.

下面说说a8推理过程如下：表格来自：http://blog.csdn.net/mu399/article/details/7722810

(1)由于物体a质量2<8,因此根据推导公式判断b8和 b6+6(value)二者取大值

（2）由表可知，b8=9，b6=9, b6+6(value)=15,所以取值15；

其它取值过程类似。

代码实现如下：

 1 #include<iostream>
 2 using namespace std;
 3 int c[200][200];//前i个物品装入容量为j的背包中获得的最大价值
 4 int max(int a,int b)
 5 {
 6    if(a>=b)
 7        return a;
 8    else return b;
 9 }
10 
11 int KnapSack(int n,int w[],int v[],int x[],int C)//w 物品的重量 v物品的价值  x 物品的选取状态 C背包最大容量
12 {
13     int i,j;
14     for(i=0;i<=n;i++)
15         c[i][0]=0;
16     for(j=0;j<=C;j++)
17         c[0][j]=0;
18     for(i=0;i<=n-1;i++)
19         for(j=0;j<=C;j++)
20             if(j<w[i])//i物品重量超过j
21                c[i][j]=c[i-1][j];
22             else
23                 c[i][j]=max(c[i-1][j],c[i-1][j-w[i]]+v[i]);//不选用i物品和选用i物品之间选最大的
24             j=C;
25             for(i=n-1;i>=0;i--)
26             {
27               if(c[i][j]>c[i-1][j])//选用i物品
28               {
29                 x[i]=1;
30                 j=j-w[i];
31               }
32             else
33                 x[i]=0;
34             }
35        cout<<"the select ting:"<<endl;
36             for(i=0;i<n;i++)
37               cout<<x[i]<<" ";
38              cout<<endl;
39         return c[n-1][C];
40 
41 }
42 
43 int main()
44 {
45     int s;//获得的最大价值
46     int w[15];//物品的重量
47     int v[15];//物品的价值
48     int x[15];//物品的选取状态
49     int n,i;
50     int C;//背包最大容量
51     cout<<"enter the max weight:C=";
52     cin>>C;
53     cout<<"enter the number :n=";
54     cin>>n;
55    cout<<"enter the weight of n thing:";
56     for(i=0;i<n;i++)
57           cin>>w[i];
58  cout<<"enter the value of n thing:";
59     for(i=0;i<n;i++)
60          cin>>v[i];
61     s=KnapSack(n,w,v,x,C);
62  cout<<"the max value:"<<s;
63 return 0;
64 
65 }

测试结果如下所示：

总结

背包问题关键在于动态规划，动态规划关键在于公式的理解与掌握，加上实践。