詳細點選一下連結（背包九講）
http://love-oriented.com/pack/Index.html#sec1 以下内容，有些自己想法，有些摘錄
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~·································~~~~~~~~~~~~~~~~~~~~~~···································~~~~~~~~~~~~~~······················~~~~~~~~
動态規劃算法可分解成從先到後的4個步驟：
1. 描述一個最優解的結構；
2. 遞歸地定義最優解的值；
3. 以“自底向上”的方式計算最優解的值；
4. 從已計算的資訊中建構出最優解的路徑。
其中步驟1~3是動态規劃求解問題的基礎。如果題目隻要求最優解的值，則步驟4可以省略。
背包---------01背包問題
每種物品可以選擇放進背包或者不放進背包（這也就是0和1）
設背包容量為V，一共N件物品，每件物品體積為C[i]，每件物品的價值為W[i]
1） 子問題定義：F[i][j]表示前i件物品中選取若幹件物品放入剩餘空間為j的背包中所能得到的最大價值。
2） 根據第i件物品放或不放進行決策
(1-1)
優化空間複雜度 -----要嘗試了解，看了很多人的代碼，都是用這個的
以上方法的時間和空間複雜度均為O(VN)，其中時間複雜度應該已經不能再優化了，但空間複雜度卻可以優化到O。
先考慮上面講的基本思路如何實作，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果隻用一個數組f[0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]儲存的是狀态f[i-1][v-c[i]]的值。僞代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當于我們的轉移方程
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}
，因為現在的f[v-c[i]]就相當于原來的f[i-1][v-c[i]]。如果将v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是完全背包問題最簡捷的解決方案，故學習隻用一維數組解01背包問題是十分必要的。
事實上，使用一維數組解01背包的程式在後面會被多次用到，是以這裡抽象出一個處理一件01背包中的物品過程，以後的代碼中直接調用不加說明。
過程ZeroOnePack，表示處理一件01背包中的物品，兩個參數cost、weight分别表明這件物品的費用和價值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意這個過程裡的處理與前面給出的僞代碼有所不同。前面的示例程式寫成v=V..0是為了在程式中展現每個狀态都按照方程求解了，避免不必要的思維複雜度。而這裡既然已經抽象成看作黑箱的過程了，就可以加入優化。費用為cost的物品不會影響狀态f[0..cost-1]，這是顯然的。
有了這個過程以後，01背包問題的僞代碼就可以這樣寫：
for i=1..N
ZeroOnePack(c[i],w[i]); ps：初始化問題
（1）：要求恰好裝滿背包，那麼在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解
初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀态。如果要求背包恰好裝滿，那麼此時隻有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀态，它們的值就都應該是-∞了。
（2）：如果并沒有要求必須把背包裝滿，而是隻希望價格盡量大，初始化時應該将f[0..V]全部設為0
如果背包并非必須被裝滿，那麼任何容量的背包都有一個合法解“什麼都不裝”，這個解的價值為0，是以初始時狀态的值也就全部為0了。
典例加深
51nod 1085 背包問題V1
在N件物品取出若幹件放在容量為W的背包裡，每件物品的體積為W1，W2……Wn（Wi為整數），與之相對應的價值為P1,P2……Pn（Pi為整數）。求背包能夠容納的最大價值。
Input
第1行，2個整數，N和W中間用空格隔開。N為物品的數量，W為背包的容量。(1 <= N <= 100，1 <= W <= 10000)
第2 - N + 1行，每行2個整數，Wi和Pi，分别是物品的體積和物品的價值。(1 <= Wi, Pi <= 10000) Output
輸出可以容納的最大價值。 Input示例
3 6
2 5
3 8
4 9 Output示例
14
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 int value[105],tiji[105];
5 int dp[10005],num,m,i,j;
6 int main(){
7 cin>>num>>m;
8 for(i=0;i<num;i++)
9 cin>>tiji[i]>>value[i];
10 memset(dp,0,sizeof(dp));
11 for(i=0;i<num;i++)
12 for(j=m;j>=tiji[i];j--)8
13 dp[j]=max((dp[j-tiji[i]]+value[i]),dp[j]);
14 cout<<dp[m];
15 return 0;
16 } hdoj 2546 飯卡 （01背包變形）
Problem Description
電子科大學部食堂的飯卡有一種很詭異的設計，即在購買之前判斷餘額。如果購買一個商品之前，卡上的剩餘金額大于或等于5元，就一定可以購買成功（即使購買後卡上餘額為負），否則無法購買（即使金額足夠）。是以大家都希望盡量使卡上的餘額最少。
某天，食堂中有n種菜出售，每種菜可購買一次。已知每種菜的價格以及卡上的餘額，問最少可使卡上的餘額為多少。
Input
多組資料。對于每組資料：
第一行為正整數n，表示菜的數量。n<=1000。
第二行包括n個正整數，表示每種菜的價格。價格不超過50。
第三行包括一個正整數m，表示卡上的餘額。m<=1000。
n=0表示資料結束。
Output
對于每組輸入,輸出一行,包含一個整數，表示卡上可能的最小餘額。
Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
Sample Output
-45
32
1 #include <string.h>
2 #include <iostream>
3 #include <algorithm>
4 using namespace std;
5 int main(){
6 int n,V, w[1005],dp[1005];
7 while(cin>>n&&n){
8 memset(dp,0,sizeof(dp));
9 for(int i=1;i<=n;i++)
10 cin>>w[i];
11 cin>>V;
12 sort(w+1,w+1+n); //從1開始
13 if(V<5) cout<<V<<endl;
14 else{
15 for(int i=1;i<n;i++) //留一個名額
16 for(int j=V-5;j>=w[i];j--) //保留5元，用剩下的錢去買價值更大的菜
17 dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
18 cout<<V-dp[V-5]-w[n]<<endl; //餘額-最多能買的菜-最貴的菜
19 }
20 }
21 return 0;
22 } poj 3624 Charm Bracelet（01背包）
Description
Bessie has gone to the mall\'s jewelry store and spies a charm bracelet. Of course, she\'d like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a \'desirability\' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
Output
* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
Sample Input
4 6
1 4
2 6
3 12
2 7 Sample Output
23 1 /* G++
2 這題數組一定要開大，但也不能太大，否則都wa
3 看了discuss中讨論
4 貌似記錄數組（dp）的大小應該由M決定吧
5
6 W，D的大小是由N決定的
7 */
8 #include <stdio.h>
9 #include <string.h>
10 #define M 14000
11 int dp[M];
12 int main(){
13 int n,m,v,w;
14 memset(dp,0,sizeof(dp));
15 scanf("%d %d",&n, &m);
16 for(int i=1;i<=n;i++){
17 scanf("%d %d",&w, &v);
18 for(int j=m;j>=w;j--){
19 int temp=dp[j-w]+v;
20 if(temp>dp[j])
21 dp[j]=temp;
22 }
23 }
24 printf("%d\n",dp[m]);
25 } 一個常數優化
前面的僞代碼中有 for v=V..1，可以将這個循環的下限進行改進。
由于隻需要最後f[v]的值，倒推前一個物品，其實隻要知道f[v-w[n]]即可。以此類推，對以第j個背包，其實隻需要知道到f[v-sum{w[j..n]}]即可，即代碼中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
這對于V比較大時是有用的。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~·~~~~~~~~~~~~~~~~~·············································································································································································~~~~~~~~~~~~~~~~~~~~~~~~~·
背包---------完全背包問題
有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
與01背包不同就是每種物品無限件可用，也就是從每種物品的角度考慮，與它相關的政策已并非取或者不取兩種了，而是有取0件，取1件，取2件
……等很多種。如果仍然按照解01背包時的思路，令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的政策寫出狀态轉移方程，像這樣：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
這跟01背包問題一樣有O(VN)個狀态需要求解，但求解每個狀态的時間已經不是常數了，求解狀态f[i][v]的時間是O(v/c[i])，總的複雜度可以認為是O(V*Σ(V/c[i]))，是比較大的。
是以要将01背包問題的基本思路加以改進
一個簡單有效的優化
完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則将物品j去掉，不用考慮。這個優化的正确性顯然：任何情況下都可将價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對于随機生成的資料，這個方法往往會大大減少物品的件數，進而加快速度。然而這個并不能改善最壞情況的複雜度，因為有可能特别設計的資料可以一件物品也去不掉。
這個優化可以簡單的O(N^2)地實作，一般都可以承受。另外，針對背包問題而言，比較不錯的一種方法是：首先将費用大于V的物品去掉，然後使用類似計數排序的做法，計算出費用相同的物品中價值最高的是哪個，可以O(V+N)地完成這個優化。這個不太重要的過程就不給出僞代碼了，希望你能獨立思考寫出僞代碼或程式。
轉化為01背包問題求解
既然01背包問題是最基本的背包問題，那麼我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c[i]件，于是可以把第i種物品轉化為V/c[i]件費用及價值均不變的物品，然後求解這個01背包問題。這樣完全沒有改進基本思路的時間複雜度，但這畢竟給了我們将完全背包問題轉化為01背包問題的思路：将一種物品拆成多件物品。
更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若幹件物品，其中k滿足
c[i]*2^k<=V
。這是二進制的思想，因為不管最優政策選幾件第i種物品，總可以表示成若幹個2^k件物品的和。這樣把每種物品拆成O(log V/c[i])件物品，是一個很大的改進。
但我們有更優的O(VN)的算法。
O(VN)的算法
這個算法使用一維數組，先看僞代碼：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
想必大家看出了和01背包的差別，這裡的内循環是順序的，而01背包是逆序的。
現在關鍵的是考慮：為何完全背包可以這麼寫？
在次我們先來回憶下，01背包逆序的原因？是為了是max中的兩項是前一狀态值，這就對了。
那麼這裡，我們順序寫，這裡的max中的兩項當然就是目前狀态的值了，為何？
因為每種背包都是無限的。當我們把i從1到N循環時，f[v]表示容量為v在前i種背包時所得的價值，這裡我們要添加的不是前一個背包，而是目前背包。是以我們要考慮的當然是目前狀态。
總結
事實上，對每一道動态規劃題目都思考其方程的意義以及如何得來，是加深對動态規劃的了解、提高動态規劃功力的好方法。
典例加深
51nod 換零錢（完全背包）
N元錢換為零錢，有多少不同的換法？币值包括1 2 5分，1 2 5角，1 2 5 10 20 50 100元。
例如：5分錢換為零錢，有以下4種換法：
1、5個1分
2、1個2分3個1分
3、2個2分1個1分
4、1個5分
(由于結果可能會很大，輸出Mod 10^9 + 7的結果)
Input
輸入1個數N，N = 100表示1元錢。(1 <= N <= 100000) Output
輸出Mod 10^9 + 7的結果 Input示例
5 Output示例
4
1 /*
2 dp[i]表示錢i能換零錢的種類數，
3 那麼每次換的時候有兩種情況
4 dp[i]表示不換，dp[i-v[j]]表示換了，
5 其和便是答案，換與不換其實是利用到了前邊的
6 計算結果
7 */
8 #include <iostream>
9 #include <stdio.h>
10 using namespace std;
11 const int maxn=100005;
12 const int mod=1e9+7;
13 int n;
14 long long dp[maxn];
15 int v[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};
16
17 int main(){
18 scanf("%d",&n);
19 dp[0]=1;
20 for(int j=0;j<13;j++)
21 for(int i=v[j];i<=n;i++)
22 dp[i]=(dp[i]+dp[i-v[j]])%mod;
23 printf("%I64d\n",dp[n]); //printf("%lld\n",dp[n]);
24 return 0;
25 } hdoj 1114 Piggy-Bank（完全背包）
Problem Description
Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.
But there is a big problem with piggy-banks. It is not possible to
determine how much money is inside. So we might break the pig into pieces only
to find out that there is not enough money. Clearly, we want to avoid this
unpleasant situation. The only possibility is to weigh the piggy-bank and try to
guess how many coins are inside. Assume that we are able to determine the weight
of the pig exactly and that we know the weights of all coins of a given
currency. Then there is some minimum amount of money in the piggy-bank that we
can guarantee. Your task is to find out this worst case and determine the
minimum amount of cash inside the piggy-bank. We need your help. No more
prematurely broken pigs!
Input
The input consists of T test cases. The number of them
(T) is given on the first line of the input file. Each test case begins with a
line containing two integers E and F. They indicate the weight of an empty pig
and of the pig filled with coins. Both weights are given in grams. No pig will
weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second
line of each test case, there is an integer number N (1 <= N <= 500) that
gives the number of various coins used in the given currency. Following this are
exactly N lines, each specifying one coin type. These lines contain two integers
each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of
the coin in monetary units, W is it\'s weight in grams.
Output
Print exactly one line of output for each test case.
The line must contain the sentence "The minimum amount of money in the
piggy-bank is X." where X is the minimum amount of money that can be achieved
using coins with the given total weight. If the weight cannot be reached
exactly, print a line "This is impossible.".
Sample Input
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
Sample Output
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
1 #include <string.h>
2 #include <stdio.h>
3 #include <algorithm>
4 using namespace std;
5
6 int dp[1000005];
7
8 int main()
9 {
10 int t;
11 int wa,wb,w;
12 int n,val[505],wei[505],i,j;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d%d",&wa,&wb);
17 w = wb-wa;//必須減去小豬本身重量
18 scanf("%d",&n);
19 for(i = 0;i<n;i++)
20 scanf("%d%d",&val[i],&wei[i]);
21 for(i = 0;i<=w;i++)
22 {
23 dp[i] = 10000000;//因為要求小的，是以dp數組必須存大數
24 }
25 dp[0] = 0;
26 for(i = 0;i<n;i++)
27 {
28 for(j = wei[i];j<=w;j++)
29 {
30 dp[j] = min(dp[j],dp[j-wei[i]]+val[i]);
31 }
32 }
33 if(dp[w] == 10000000)
34 printf("This is impossible.\n");
35 else
36 printf("The minimum amount of money in the piggy-bank is %d.\n",dp[w]);
37 }
38
39 return 0;
40 } ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~···········································································································~~~~~~~~~~~~~~~~~~~~~~
多重背包問題
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
這題目和完全背包問題很類似。基本的方程隻需将完全背包問題的方程略微一改即可，因為對于第i種物品有n[i]+1種政策：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則有狀态轉移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
複雜度是O(V*Σn[i])。
轉化為01背包問題
另一種好想好寫的基本方法是轉化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數為Σn[i]的01背包問題，直接求解，複雜度仍然是O(V*Σn[i])。
但是我們期望将它轉化為01背包問題之後能夠像完全背包一樣降低複雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若幹件物品，使得原問題中第i種物品可取的每種政策——取0..n[i]件——均能等價于取若幹件代換以後的物品。另外，取超過n[i]件的政策必不能出現。
方法是：将第i種物品分成若幹件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分别為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數。例如，如果n[i]為13，就将這種物品分成系數分别為1,2,4,6的四件物品。
2^0+2^1+2^2+（2^3）>13
是以，13-2^0-2^1-2^2=6
這四個數可以組成13中任意一個數 7=6+1, 5=4+1……
分成的這幾件物品的系數和為n[i]，表明不可能取多于n[i]件的第i種物品。另外這種方法也能保證對于0..n[i]間的每一個整數，均可以用若幹個系數的和表示，這個證明可以分0..2^k-1和2^k..n[i]兩段來分别讨論得出，并不難，希望你自己思考嘗試一下。
這樣就将第i種物品分成了O(log n[i])種物品，将原問題轉化為了複雜度為<math>O(V*Σlog n[i])的01背包問題，是很大的改進。
下面給出O(log amount)時間處理一件多重背包中物品的過程，其中amount表示物品的數量：
procedure MultiplePack(cost,weight,amount)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
希望你仔細體會這個僞代碼，如果不太了解的話，不妨翻譯成程式代碼以後，單步執行幾次，或者頭腦加紙筆模拟一下，也許就會慢慢了解了。
51nod 1086 背包問題V2（多重背包）
有N種物品，每種物品的數量為C1，C2......Cn。從中任選若幹件放在容量為W的背包裡，每種物品的體積為W1，W2......Wn（Wi為整數），與之相對應的價值為P1,P2......Pn（Pi為整數）。求背包能夠容納的最大價值。
Input
第1行，2個整數，N和W中間用空格隔開。N為物品的種類，W為背包的容量。(1 <= N <= 100，1 <= W <= 50000)
第2 - N + 1行，每行3個整數，Wi，Pi和Ci分别是物品體積、價值和數量。(1 <= Wi, Pi <= 10000， 1 <= Ci <= 200) Output
輸出可以容納的最大價值。 Input示例
3 6
2 2 5
3 3 8
1 4 1 Output示例
9
1 //思路：二進制 + 01背包思想
2 #include <iostream>
3 #include<cstdio>
4 #include<cmath>
5 int w,va,c,w1[10010],va1[10010];
6 int dp[50010];
7 using namespace std;
8
9 int main()
10 {
11 int N,W;
12 int cnt=0;//二進制之後的物件個數
13 scanf("%d%d",&N,&W);
14 for(int i=1;i<=N;i++) {
15 scanf("%d%d%d",&w,&va,&c);
16 for(int j=1;;j*=2) {
17 if(c>=j){
18 w1[cnt]=j*w;
19 va1[cnt]=j*va;
20 c-=j;
21 cnt++;
22 }
23 else {
24 w1[cnt]=c*w;
25 va1[cnt]=c*va;
26 cnt++;
27 break;
28 }
29 }
30 }
31 for(int i=0;i<cnt;i++){
32 for(int j=W;j>=w1[i];j--)
33 dp[j]=max(dp[j],dp[j-w1[i]]+va1[i]);
34 }//一維 空間複雜度小
35 printf("%d\n",dp[W]);
36 return 0;
37 }