有限背包 | Axell's Blog

有限背包

设第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;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/90/