如果物品可以拆分,則問題稱為背包問題,適合使用貪心算法
給定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 }
文章列表