背包問題--動态規劃

背包問題

     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	6	6	9	9	12	12	15	15	15
b	2	3	3	3	6	6	9	9	9	10	11
c	6	5	6	6	6	6	6	10	11
d	5	4	6	6	6	6	6	10	10
e	4	6	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 }      

  測試結果如下所示：

總結

   背包問題關鍵在于動态規劃，動态規劃關鍵在于公式的了解與掌握，加上實踐。

轉載于:https://www.cnblogs.com/zhanjxcom/p/5819981.html