背包問題
題意：給出背包的容量，以及一批物品的價值和大小，求最大價值。
01背包問題
題意
每個物品只能放入一次。
思路
用f[i][v]表示，第i個大小為v的物品放入時的總價值。
c[i]表示第i個物品的價值。w[i]為第i個物品的大小。
狀態(tài)轉(zhuǎn)移方程：f[i][v] = max(f[i-1][v], f[i-1][v-w[i]]+c[i]);
狀態(tài)轉(zhuǎn)移方程表示，取放入或者不放入第i個物品兩種情況的最大值。
空間優(yōu)化（滾動數(shù)組）
初始狀態(tài)方程的空間復(fù)雜度是O(V*W)，可以進一步優(yōu)化。
可以將空間優(yōu)化為O(2*W)，即縱向大小為2。
for(i=1; i<=N; i++){
for(j=t[i]; j<=V; j++)
f[t^1][j] = max(f[c][j-w[i]]+c[i], f[t][j]);
t ^= 1;
}
異或滾動可以在0和1之間切換，可以利用上下反復(fù)更新。
空間優(yōu)化（一維數(shù)組）
既然可以用兩行進行更新，那為什么不能用一行。
觀察問題，兩行更新時，用上一行的前部分更新下一行的后部分。
所以單行更新時要從后往前遍歷，這樣可以用前面的更新后面的。
for(i=1; i<=N; i++)
for(j=V; j>=w[i]; j--)
f[j] = max(f[j-w[i]]+c[i], f[j]);
這樣就可以用一維數(shù)組來進行更新。
可以寫成函數(shù)，封裝起來。
void ZeroOnePack(int cost, int weight){
for(int i=V; i>=weight; i++)
f[i] = max(f[i], f[i-weight]+cost)
}
初始化的細節(jié)問題
一般問題會有兩種問法：
- 剛好裝滿背包
- 不用裝滿背包
如果是第一種，f[0]=0,f[1]……f[N]=INF;
如果是第二種，f[0]……f[N]=INF;
理解：
如果是第一種，初始狀態(tài)只有0符合理想狀態(tài)，只有0才能被空“裝滿”。
如果是第二種，所有都符合理想狀態(tài)。
完全背包問題
題意
和01背包相似，所不同的是可取的物品數(shù)是無限。
前置小優(yōu)化
對于i``j兩個物品，如果c[i]>c[j] && w[i]<w[j]，就舍去i物品。
另外，針對背包問題而言，比較不錯的一種方法是：首先將重量大于V的物品去掉，然后使用類似計數(shù)排序的做法，計算出費用相同的物品中價值最高的是哪個，可以O(shè)(V+N)地完成這個優(yōu)化。
基本思路
狀態(tài)轉(zhuǎn)移方程f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]},(0<=k*w[i]<=V)
轉(zhuǎn)化為01背包求解
一件物品最多只能放V/c[i]件，所以可以把一件物品，看成V/c[i]件物品，作為01背包解答。
另一種更好的辦法是把第i種物品拆成大小為w[i]*2^k、價值為c[i]*2^k的若干件物品，其中k滿足w[i]*2^k<=V。這是二進制的思想，因為不管最優(yōu)策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log(V/w[i]))件物品，是一個很大的改進。
O(VN)算法
for(int i=1; i<=N; i++)
for(int j=w[i]; j<=V; j++)
f[j] = max{f[v], f[v-w[i]]+c[i]};
這個算法和之前的01背包相比只是第二層的遍歷方向改變了。因為01背包要保證每個物品只能選擇一次，但是完全背包不必，所以改變遍歷方向就可以得到結(jié)果。
這個算法也可以從另外的思路中得出，例如，基本思路中的公式可以化作這個形式：f[i][v]=max(f[i-1][v], f[i][v-w[i]]+c[i]);
用函數(shù)封裝：
void CompletePack(int cost, int weight){
for(int i=weight; i<=V; i++)
f[i] = max(f[i], f[i-weight]+cost);
}
多重背包問題
題意
每件物品數(shù)量不一定為1但有限。
基本思路
問題和完全背包很相似。
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[I]}(0<=k<=n[I])
復(fù)雜度為O(V*Σn[i])。
轉(zhuǎn)化為01背包問題
用n[i]存儲，可以將每種物品轉(zhuǎn)化為n[i]件物品，然后用01背包方案求解。復(fù)雜度不變。
如果要進行優(yōu)化的話，依然用二進制思想，同上。
這樣可以將時間優(yōu)化為O(V*Σlog n[i])。
void MultiplePack(int weight, int cost, int amount){
if(cost * amount >= V){
CompletePack(cost, weight);
return;
}
int k = 1;
while(k < num){// num 為物品種數(shù)
ZeroOnePack(k*cost, k*weight);
amount = amount-k;
k *= 2;
}
ZeroOnePack(amount*cost, amount*weight);
}
