完全背包讲解

裸题洛谷P1616疯狂的采药

本题为采药进化版   和采药的区别为  每种药材有无数多个  且可以多次采摘同种药材

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

那么很容易想到完全背包

下面放ac代码

#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
typedef long long ll;
int t,m,dp[100005],w[10005],v[10005];
int main(int argc, char const *argv[])
{
    scanf("%d%d",&t,&m);
    rep(i,m)
    {
        scanf("%d%d",&w[i],&v[i]);
    }
    rep(i,m)
    {
        for(int j=w[i];j<=t;j++)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    printf("%d\n",dp[t]);
    return 0;
}

那么

整个代码精髓如下

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

其中rep为for(int i=1;i<=m;i++)   (我比较懒  用define重新定义了下)

那么我们可以看到  这段代码和01背包 一维数组优化只差一点点

就是 内层for循环 使用的是顺序 而不是逆序

其实我也不太理解

那么就用我微薄的知识 简单解释一下吧

我认为（逃

和01背包的不同就在于 01背包类似于打表 每次一定要使用上组数据进行dp

而完全背包不一样 因为可以重复选择 所以内层循环顺序可以使得使用本组数据dp 这样可以造成重复选择的结果（逃

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄