文章出處

給定一個物品集合s={1,2,3,…,n},物品i的重量是wi,其價值是vi,背包的容量為W,即最大載重量不超過W。在限定的總重量W內,我們如何選擇物品,才能使得物品的總價值最大。
如果物品不能被分割,即物品i要么整個地選取,要么不選取;
不能將物品i裝入背包多次,也不能只裝入部分物品i,則該問題稱為0—1背包問題。

如果物品可以拆分,則問題稱為背包問題,適合使用貪心算法

給定n種物品和一背包。物品i的重量是wi,其價值為vi,背包的容量為C。問:應如何選擇裝入背包的物品,使得裝入背包中物品的總價值最大?

     設(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)不是背包問題的最優解,矛盾。

      遞推關系:

    設所給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 ; (3) 對于最后一個物品n , 如果 j>=Wn,則肯定裝入, 獲得價值Vn; 如果0<=j < Wn,則無法裝入, 獲得的價值為 0 。

 

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 #define NUM 50              //物品數量的上界 
 6 #define CAP 1500            //背包容量的上界 
 7 int v[NUM];                 //物品的重量 
 8 int w[NUM];                 //物品的價值 
 9 int p[NUM][CAP];            //用于遞歸的數組。
10 //形參 c 是背包的容量 W,n是物品的數量。 
11 void knapsack(int c, int n) 
12 { 
13     //計算遞推邊界 
14     int jMax=min(w[n]-1,c);   //分界點。 
15     for( int j=0; j<=jMax; j++) 
16         p[n][j]=0; 
17     for( int j=w[n]; j<=c; j++) 
18         p[n][j]=v[n];
19     for( int i=n-1; i>1; i--)//計算遞推式 
20     { 
21         jMax=min(w[i]-1,c); 
22         for( int j=0; j<=jMax; j++) 
23             p[i][j]=p[i+1][j]; 
24         for(int j=w[i]; j<=c; j++) 
25             p[i][j]=max(p[i+1][j], p[i+1][j-w[i]]+v[i]); 
26     } 
27     p[1][c]=p[2][c];         //計算最優值。 
28     if (c>=w[1]) 
29         p[1][c]=max(p[1][c], p[2][c-w[1]]+v[1]); 
30 } 
31 //形參數組 x 是解向量。 
32 void traceback( int c, int n, int x[]) 
33 { 
34     for(int i=1; i<n; i++) 
35     {
36         if (p[i][c]==p[i+1][c]) x[i]=0; 
37         else { x[i]=1; c-=w[i]; } 
38     }
39     x[n]= (p[n][c]) ? 1:0; 
40 } 
41 
42 int main () 
43 {
44     int x[NUM];
45     int W;
46     int n;
47     while (scanf("%d", &W) && W) 
48     {
49         scanf("%d", &n);
50         for (int i=1; i<=n; i++)
51             scanf("%d%d", &w[i], &v[i]);
52         memset (p, 0, sizeof(p));
53         knapsack(W, n);
54         printf("%d\n", p[1][W]);
55         traceback(W, n, x);
56         for (int i=1; i<=n; i++)
57             if (x[i]) printf("%d ", i);
58         printf("\n");
59     }
60     return 0;
61 }
View Code

 

 

 


文章列表


不含病毒。www.avast.com
arrow
arrow
    全站熱搜
    創作者介紹
    創作者 大師兄 的頭像
    大師兄

    IT工程師數位筆記本

    大師兄 發表在 痞客邦 留言(0) 人氣()