今天主要看一下经典的背包问题：
01背包Charm Bracelet
有N件物品和一个容积为M的背包。第i件物品的体积w[i] ，价值是d[i]。求解将哪些物品装入背包可使价值总和 最大。每种物品只有一件，可以选择放或者不放 (N<=3500,M <= 13000)
example:
总体积：6 物品数：4
体积： 1 2 3 2
价值： 4 6 12 7
取舍： 1 0 1 1
结果：23
我们设V[i][j]表示前i个物品，体积不超过j，取得的最大价值。于是：
V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]]+d[i])//表示在满足不超过j的情况下，对第i个物品进行取舍
#include <iostream>
#include <algorithm>
#include <string.h>
usingnamespacestd;
int main() {
int N,M;
cin>>N>>M;
int W[N + 1],D[N + 1];//W是重量，D是期望度
for (int i = 1; i <= N; i++) {
cin>>W[i]>>D[i];
}
int MaxDesire[N + 1][M + 1];
memset(MaxDesire, 0, sizeof(MaxDesire));
for (int i = 1; i <= M; i++) {
if (i >= W[1]) {
MaxDesire[1][i] = D[1];
} else MaxDesire[1][i] = 0;
}
for (int i = 2; i <= N; i++) {
for (int j = 0; j <= M; j++) {
MaxDesire[i][j] = MaxDesire[i - 1][j];
if (j - W[i] >= 0) {
MaxDesire[i][j] = max(MaxDesire[i - 1][j - W[i]] + D[i], MaxDesire[i - 1][j]);
}
}
}
cout<<MaxDesire[N][M];
return0;
}
但是，这个题目如果这么开二维数组的话，就会超内存，我们得想一种更节省内存的办法。
即考虑：对这些物品而言，不超过j能达到的最大价值，我们设成MaxV[j]。动态规划，要求无后效性，而对前i种物品考虑的取舍，对i种以后的物品取舍，有无后效性（对比，三角形那的滚动数组）
#include <iostream>
#include <algorithm>
#include <string.h>
usingnamespacestd;
int main() {
int N,M;
cin>>N>>M;
int W[N + 1],D[N + 1];//W是重量，D是期望度
for (int i = 1; i <= N; i++) {
cin>>W[i]>>D[i];
}
int MaxDesire[M + 1];
memset(MaxDesire, 0, sizeof(MaxDesire));
for (int i = 1; i <= N; i++) {
for (int j = M; j >= W[i]; j--) {
MaxDesire[j] = max(MaxDesire[j - W[i]] + D[i], MaxDesire[j]);
}
}
cout<<MaxDesire[M]<<endl;
return0;
}
神奇的口袋
神奇的口袋(百练2755)
有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。
John现在有n(1≤n ≤ 20)个想要得到的物品，每个物品的体积分别是a1，a2......an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式
这道题有两种解法，一种是传统的递归式解法，另外一种是可达型动态规划，设计更加巧妙一些，当作练习题。【Tips:一维动规】
我们设Ways[i][j]表示用前j件物品凑出i体积的方法数，而题目要求我们求的就是Ways[40][N],那么：
* 如果前j-1件物品可以组成i, 那么前j件物品也可以组成i
* 如果前j-1件物品可以组成i-a[j](所以必须是i-a[i]大于零的情况)，那么前j件物品也可以组成i
#include <iostream>
#include <algorithm>
#include <string.h>
usingnamespacestd;
int main() {
int t;
cin>>t;
int A[t];
int Ways[41][t + 1];
memset(Ways, 0, sizeof(Ways));
for (int i = 0; i < t; i++) {
cin>>A[i];
}
for (int i = 0; i <= t; i++) {
Ways[0][i] = 1;
}
for (int i = 0; i <= 40; i++) {
for (int j = 1; j <= t; j++) {
Ways[i][j] = Ways[i][j - 1];
if (i - A[j - 1] >= 0) {
Ways[i][j] = Ways[i][j - 1] + Ways[i - A[j - 1]][j - 1];
}
}
}
for (int i = 0; i <= 40; i++) {
for (int j = 0; j <= t; j++) {
cout<<Ways[i][j]<<" ";
}
cout<<i<<endl;
}
cout<<Ways[40][t];
return0;
}
练习题：
用一维动规解决神奇的口袋
最佳加法表达式(百练上的版本要求高精度)
