0-1背包問題

問題：

有N件物品和一個容量為V的背包。第i件物品的價值是c[i]，重量是w[i]。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。

這個問題的特點是：每種物品只有一件，可以選擇放或者不放。用f[i][j]表示背包當前容量為j,選擇裝入1-i個物品時的最大價值

在求最優解的背包問題中，一般有兩種不同的問法：1、求小於等於背包容量的最優解，即不一定恰好裝滿背包;2、要求“恰好裝滿背包”時的最優解.

1、求小於等於背包容量的最優解，即不一定恰好裝滿背包;

設f[0..N][0..v]=0

2、要求“恰好裝滿背包”時的最優解.

則f[0][1..v]=-∞,確保當背包不滿時得不到最優解（價值最大）

狀態轉移方程：

1. f[i][j]=f[i-1][j]         j<w[i-1]
2. f[i][j]=max{f[i-1][j].f[i-1][j-w[i-1]]+c[i-1]}        其它

解釋：

1.背包當前容量j小於第i件物品的重量w[i-1]，第i件物品裝不下，所有不放第i件物品

2.第i件物品可以放下，進行選擇，放或者不放

• 如果不放，則問題轉化為“前i-1件物品放入容量為j的背包中”
• 如果放，則問題轉化為“前i-1件物品放入剩下的容量為j-w[i-1]的背包中”，此時能獲得的最大的價值就是f[i-1][j-w[i-1]]再加上通過放入第i件物品獲得的價值c[i-1]

在“其它”情況下，f[i][j]的值就是上述兩種情況中的最大值

代碼：

 1 #include<iostream>
 2 using namespace std;
 3 int f[100][100];
 4 int Min=-999999;
 5 int package(int n,int v,int w[],int c[])    //n-物品數量，v-背包容量，w[]各個物品的重量，c[]對應物品的價值
 6 {
 7     if(f[n][v]!=0)                    //已計算過該子問題
 8         return f[n][v];
 9     if(n==0||v<=0)      //題型一：價值最大，不要求裝滿
10         return 0;
11 
12     //if(n==0)    //題型二：背包裝滿的情況下最大價值，設f[0][0]=0，f[0][1..v]=-∞，即當背包不滿時沒有最優解
13     //{
14     //    if(v!=0) return Min;
15     //    return 0;
16     //}
17 
18     if(v<w[n-1])           //第n件物品的重量大於當前背包的容量，則不裝第n件物品，背包容量仍為v，從剩餘的n-1件物品中選擇
19         f[n][v]=package(n-1,v,w,c);
20     else               //背包當前容量可以裝下第n件物品，可以選擇裝或者不裝第n件物品
21     {
22         int a=package(n-1,v,w,c);      //不裝第n件物品，從剩餘的n-1件物品中選擇，背包容量仍為v
23         int b=package(n-1,v-w[n-1],w,c)+c[n-1];   //裝第n件物品，則當前價值為第n件物品的價值c[n]加上(n-1,v-w[n])問題的最優解
24         f[n][v]=a>b?a:b;            //選擇價值最大的解
25     }
26     return f[n][v];
27 }
28 
29 int main()
30 {
31     memset(f,0,sizeof(f));    //設置邊界條件
32     int n,v,w[100],c[100];
33     cout<<"input the number of items:";
34     cin>>n;
35     cout<<"input the volume of items:";
36     cin>>v;
37     cout<<"input the weight of items:";
38     for(int i=0;i<n;i++)
39         cin>>w[i];
40     cout<<"input the value of items:";
41     for(int i=0;i<n;i++)
42         cin>>c[i];
43     cout<<"the bigest value is:";
44     cout<<package(n,v,w,c)<<endl;
45 }

結果：

問法一：求小於等於背包容量的最優解，即不一定恰好裝滿背包;

問法二：要求“恰好裝滿背包”時的最優解.