最近搞了许多背包的题，总结一下各自用法：
01背包：各个商品最多一件，用for（）时倒序保证只能取一次；
完全背包：各个商品无限件，用for（）时正序保证在背包范围内能一直取；
多重背包：各个商品有a[i]件，对每个商品进行讨论，分成完全背包与01背包，拆分只学会了二进制拆分，代码如下：
int ans=cnt[i],s=1; while(s<=ans) { for(int j=C;j>=w[i]*s;j--) f[j]=max(f[j],f[j-w[i]*s]+v[i]*s); ans-=s;s=s<<1; } for(int j=C;j>=w[i]*ans;j--) f[j]=max(f[j],f[j-w[i]*ans]+v[i]*ans);
混合背包：分成以上各个背包；
遇到一道二维背包的题，搞了许久：
很明显需要的O与N很小，但是各个气缸所累加的O，N就大多了，故背包的数组不能由各个气缸所累加的O，N决定；
这个时候就要转换思维了,见以下代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1100; int O,N,n,w[maxn],a[maxn],b[maxn],f[30][80]; //f[j][k]表示前i个气缸O为j，N为k时的最小重量。 inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') ff=-1; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*ff; } inline void DP() { for(int i=1;i<=n;i++) //依次枚举各个商品... for(int j=O;j>=0;j--) //01背包，倒序枚举各个O的容量... for(int k=N;k>=0;k--) //01背包，倒序枚举各个N的容量... { int T=j-a[i]; //1;用T表示O由上一个状态哪一个容量更新的... int L=k-b[i]; //2;用L表示N由上一个状态哪一个容量更新的... if(T<0) T=0; //最难理解的地方：由于所有气缸的总O，N的含量太大空间肯定 if(L<0) L=0; //开不下于是就要把符合条件的给缩小，即超过需要的就变成需要的 . f[j][k]=min(f[j][k],f[T][L]+w[i]); } //这里对其他的转移没有影响，（假如本状态由未超过需要的O与N转移得到则没有影响。 } //假如由超过需要的转移过来，那就不用考虑，直接赋成0，加上当前的重量。） int main() { freopen("1.in","r",stdin); O=read();N=read();n=read(); for(int i=1;i<=n;i++) { a[i]=read(); b[i]=read(); w[i]=read(); } memset(f,127,sizeof(f)); f[0][0]=0; DP(); cout<<f[O][N]<<endl; return 0; }
对当初的理解确实很懵，不过我们如果从DP的本质讲，就好理解多了，由于逆序输出，只能有小的值更新大的值，由于还是01背包，每个物品只能取一次，每次遇到新的容量，我们都面临取不取的问题，
不取则状态不变，取就要找到由哪一个状态转移过来，1,2就是这个意思，很明显如果T或L的值是负的即这一个缸的O，N就够需求了不需其他缸了，就可以直接把它的上一个状态设为f[0][0]这样就不会因大小问题干扰状态的转移了。这道题就完了。