完全背包

作者: Tsukinousag | 来源:发表于2021-02-19 10:26 被阅读0次

完全背包

原题链接

有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。

第 i 种物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

  • 无优化版本

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k*v[i]<=j;k++)
                dp[i][j]=max(dp[i][j],dp[i][j-k*v[i]]+k*w[i]);
    
    cout<<dp[n][m]<<endl;
  • 优化时间复杂度

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
                dp[i][j]=dp[i-1][j];
                if(j>=v[i])
                    dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
        }
    
    cout<<dp[n][m]<<endl;
  • 滚动数组优化

每种物品有无穷件

首先区别与01背包,因为物品有无穷件所以放第i件时转移到的是dp[i][x-w[i]]+c[i],在i-1时刻其存储的意义也是dp[x]记录的是前i-1个物品在容量是x时的最大值

所以x递增遍历的原因:因为放放第i件时转移到的是dp[i][x-w[i]]+c[i],对应与dp[x-v[i]]+w[i],它表示的是前i个物品在容量是x-v[i]时的最大值,所以需要正序遍历

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1010;

int n,m;
int dp[N];
int v[N],w[N];

int main()
{
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)
                    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//此时顺序枚举i,所以算的是第i时刻的dp值
    
    cout<<dp[m]<<endl;
    return 0;
}

相关文章

  • 完全背包

  • 完全背包

    有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用。第 i 种物品的费用是 c[i],价值是 w[i]...

  • 完全背包

    leetcode 322 找零钱 这道题本质上还是要3重循环来做的,只不过可以进行优化变成两重循环,在了解优化思路...

  • 完全背包

    完全背包 原题链接[https://www.acwing.com/problem/content/3/] 有 N ...

  • 背包问题(完全背包)

    动态规划合集: 1.矩阵链乘法2.投资组合问题3.完全背包问题4.01背包问题5.最长公共子序列 例题3——背包问...

  • 01背包和完全背包

    最近学习《背包问题九讲》,对0-1背包和完全背包有了新的认识。最新版本请访问 https://github.com...

  • 背包问题2(完全背包)

    01背包是指每件物品有且只有一件,而完全背包则是每件物品件数无限,求装入背包所对应的最值。完全背包也有公式,在01...

  • 算法模板(一) 01背包,多重背包,完全背包

    01背包 多重背包 完全背包

  • 动态规划完全背包01

    完全背包 和01背包一样力扣上没有没有纯完全背包问题,都是需要完全背包的各种应⽤,需要转化成完全背包问题,所以我们...

  • 完全背包问题

    相比于01背包问题只是单纯的多了一个条件:物品可以重复利用。 这是01背包问题的状态转移方程: 当W-wi大于0时...

网友评论

    本文标题:完全背包

    本文链接:https://www.haomeiwen.com/subject/qpnoxltx.html