我觉得我还是分好几篇写这个东西吧-嗷；
PACK
还有一个网站背包模板都有；AcW
1.01背包
有N">N件物品和一个容量是V">V的背包。每件物品只能使用一次。
第i">i件物品的体积是vi">vi，价值是wi">wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
思路：用已经处理好的物品作为dp的阶段，每种物品仅有一件，可以选择放或不放。
即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}；
但还可以进一步优化我们可以省去f数组的第一维，只用一维数组，f[j]表示外层循环到i时，已经装了总体积为j的物品的最大价值和；
注意j到倒序循环，这样可以保证每个物品只被选择一次。
#includeusing namespace std;#define N 500010templateinline void read(T T f=1,ch=getchar(); while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();} x*=f;}int n,v,f[N],c[N],w[N];int main(){ read(n);read(v); for(int i=1;i<=n;i++) read(c[i]),read(w[i]); for(int i=1;i<=n;i++) for(int j=v;j>=c[i];j--) f[j]=max(f[j],f[j-c[i]]+w[i]); cout<
CH 5201
n为物品，m为题解，这里我们的f[j]表示和为j的方案数，max改为求和；
#includeusing namespace std;const int maxn=1100;templateinline void read(T T f=1,ch=getchar(); while (!isdigit(ch) if (ch==‘-‘) f=-1, ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar(); x*=f;}int a[maxn],f[maxn];int main(){ int n,m; read(n);read(m); for (int i=1;i<=n;++i) read(a[i]); f[0]=1; for (int i=1;i<=n;++i) for (int j=m;j>=a[i];--j) f[j]+=f[j-a[i]]; printf("%d\n",f[m]); return 0;}View Code
2.完全背包
和01背包不同，这里的物品有无数件，当然可以考虑二维去实现，但是像01背包一样可以进行优化，当我们采用正序循环，对应每个物品可以选择无数次，
#includeusing namespace std;#define N 500010templateinline void read(T T f=1,ch=getchar(); while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();} x*=f;}int n,v,f[N],c[N],w[N];int main(){ read(n);read(v); for(int i=1;i<=n;i++) read(c[i]),read(w[i]); for(int i=1;i<=n;i++) for(int j=c[i];j<=v;j++) f[j]=max(f[j],f[j-c[i]]+w[i]); cout<
CH 5202
我们在完全背包的基础上将max改为求和就可以了；
#includeusing namespace std;const int maxn=4010;templateinline void read(T T f=1,ch=getchar(); while (!isdigit(ch) if (ch==‘-‘) f=-1, ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar(); x*=f;}int f[maxn];int main(){ int n;read(n); f[0]=1; for (int i=1;i<=n;++i) for (int j=i;j<=n;++j) f[j]=(f[j]+f[j-i])%2147483648u; printf("%d\n",f[n]>0?f[n]-1:2147483647); return 0;}View Code
3.多个体积维度的01背包；
POJ 1015
CH POJ 1015