混合背包的模板题，数量级较大应当进行优化，比如说读入优化啊，二进制优化啊。
这里说一下二进制优化，假如我们有17件物品，我们可以将其分成1,2,4,8（二的幂次方）+2（剩下的）件
这样实际上只有五件物品我们就可以拼凑出装这些物品的所有状态，然后进行标准的01背包就行了，对于无限多的，
我们可以正序循环或也采用拆分的方法。 ---背包九讲是个好东西
*************************************************************************
#include<cstdio> #include<algorithm> #define maxn 300001 using namespace std; int top=0; int wei[maxn]; int ver[maxn]; int dp[maxn]; bool note[maxn]; int n,full; int read() { int now=0; int f=1; char c=getchar(); while(c>'9'||c<'0') { if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9') { now*=10; now+=c-'0'; c=getchar(); } return now*f; } int main() { n=read();full=read(); for(int i=1;i<=n;i++) { int w=read(),v=read(),num=read(); if(num==-1) { top++; wei[top]=w; ver[top]=v; note[top]=true; continue; } int k=1; while(num>=k) { top++; wei[top]=w*k; ver[top]=v*k; num-=k; k*=2; } if(num) { top++; wei[top]=w*num; ver[top]=v*num; } } for(int i=1;i<=top;i++) { if(note[i]) { for(int j=wei[i];j<=full;j++) { dp[j]=max(dp[j],dp[j-wei[i]]+ver[i]); } } else for(int j=full;j>=wei[i];j--) { dp[j]=max(dp[j],dp[j-wei[i]]+ver[i]); } } printf("%d",dp[full]); return 0; }