完全背包讲解

裸题洛谷P1616疯狂的采药

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

那么很容易想到完全背包

下面放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
",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 这样可以造成重复选择的结果（逃

2019.4.22 更新

遇到了需要把完全背包装满的问题

要求背包必须装满求最大值

把dp[0]初始化为0，其余初始化为 $-infty$

要求背包必须装满求最小值

把dp[0]初始化为0，其余初始化为 $infty$

原因：

初始化数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义状态，应该被赋值为或者；如果背包并非必须装满，那么任何容量的背包都有一个合法解“什么也不装”，即0，所以可以把它们全部初始化为0。

人十我百人百我万