背包DP-完全背包

永安.11.23

2026-08-31 22:35:12

发布于：上海

9阅读

0回复

0点赞

完全背包：与 01 背包唯一的区别是——每种物品有无限件，可以拿任意多个
DP决策：和 01 背包完全相同，可以选择拿或者不拿

状态定义：dp[ i ][ j ]表示前 i 个物品，容量为 j 时能取到的最大价值

转移方程：

    for(int i = 1;i<=n;i++){
        for(int j = 0;j<=m;j++){
            if(j>=w[i]) dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
            else dp[i][j] = dp[i-1][j];
        }
    }

滚动数组优化：

    for(int i = 1;i<=n;i++){
        for(int j = w[i];j<=m;j++){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }

1.疯狂的采药

    for(int i = 1;i<=m;i++){
        for(int j = w[i];j<=t;j++){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }

3.Mooo Moo S

    memset(dp,0x3f,sizeof(dp));
    dp[0] = 0;
    for(int i = 1;i<=b;i++){
        for(int j = v[i];j<=100000;j++){
            dp[j] = min(dp[j],dp[j-v[i]]+1);
        }
    }

    int ans = 0;
    for(int i = 1;i<=n;i++){
        int tran = max(p[i-1]-1,0);
        int c = p[i]-tran;
        if(c<0 || dp[c]==0x3f3f3f3f){
            cout << -1;
            return 0;
        }
        ans+=dp[c];
    }

5.纪念品

    for(int i = 1;i<t;i++){ // 一共进行t-1次相邻两天的交易
        memset(dp,0,sizeof(dp));
        for(int j = 1;j<=n;j++){
            if(v[i+1][j]>v[i][j]){ // 只有明天会涨价的纪念品，今天才考虑购入
                for(int k = v[i][j];k<=m;k++){
                    dp[k] = max(dp[k],dp[k-v[i][j]]+v[i+1][j]-v[i][j]);
                    // 买一个纪念品，消耗a[i][j]元，带来a[i+1][j]-a[i][j]的利润
                }
            }
        }m+=dp[m];
    }
    cout << m;

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论