有限背包

设第i个物品有A[i]个，则在进行DP时，不能直接正/倒循环一遍，常用的方法是将同一个物品拆成若干个（二进制分解法），在用01背包的求法即可
拆分代码：

    for (int i=1;i<=n;++i){
        int tmp=1;
        while (c[i]>=tmp){
            cnt++;
            dv[cnt]=tmp*v[i];
            dw[cnt]=tmp*w[i];
            c[i]-=tmp;
            tmp<<=1;
        }
        if (c[i]){
            cnt++;
            dv[cnt]=c[i]*v[i];
            dw[cnt]=c[i]*w[i];
        }
    }

例题

goto

#include <bits/stdc++.h>
using namespace std;

int w[105],v[105],c[105],dv[3205],dw[3205],f[10005],cnt,n,mw;

int main(){
    cin>>n>>mw;
    for (int i=1;i<=n;++i) scanf("%d %d %d",&c[i],&w[i],&v[i]);
    for (int i=1;i<=n;++i){
        int tmp=1;
        while (c[i]>=tmp){
            cnt++;
            dv[cnt]=tmp*v[i];
            dw[cnt]=tmp*w[i];
            c[i]-=tmp;
            tmp<<=1;
        }
        if (c[i]){
            cnt++;
            dv[cnt]=c[i]*v[i];
            dw[cnt]=c[i]*w[i];
        }
    }
    memset(f,0x80,sizeof f);
    f[0]=0;
    int ans=-1e9;
    for (int i=1;i<=cnt;++i){
        for (int j=mw;j>=dw[i];--j){
            f[j]=max(f[j],f[j-dw[i]]+dv[i]);
            ans=max(ans,f[j]);
        }
    }
    cout<<ans<<endl;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/90/