0-1背包問題，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.背包當前容量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 }
View Code
結果：
問法一：求小於等於背包容量的最優解，即不一定恰好裝滿背包;
問法二：要求“恰好裝滿背包”時的最優解.
