背包dp

背包dp

◦一般是给出一些“物品”，每个物品具有一些价值参数和花费参数，要求

在满足花费限制下最大化价值或者方案数。

◦最简单几种类型以及模型

◦ 0/1背包

◦完全背包

◦多重背包

0/1背包

给出n个物品，每个物品有Vi的价值和Wi的费用，我们总共有m块钱，求

最多能得到多少价值的物品。

二维写法:dp[i][j]表示前i个物品,花费j元,能得到的最大价值
memset(dp,-0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
    for(int j=0;j<w[i];j++)dp[i][j]=dp[i-1][j];
    for(int j=w[i];j<=m;j++)dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}    
一维写法:f[j]表示在前i-1轮的选择后,花费j空间的背包,能得到的最大值
memset(f,-0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
    for(int j=m;j>=w[i];j--)//一定要注意枚举的顺序！！！
        f[j]=max(f[j],f[j-w[i]]+v[i]);
复杂度:O(n*m)

方案数:储存两个dp值,一个f表示最大价值，一个dp表示方案数，如果选i和不选i的最大价值相同，那么dp[j]=dp[j]+dp[j-w[i]]

具体方案:用二维dp可以很容易的用递归求出。

完全背包

问题模型：每一个物品可以选无限个

二维写法:dp[i][j]表示前i个物品,花费j元,能得到的最大价值
memset(dp,-0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
    for(int j=0;j<w[i];j++)dp[i][j]=dp[i-1][j];
    for(int j=w[i];j<=m;j++)dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);//与01背包唯一的细小差别i->i-1,dp[i-1][j-w[i]]的值已经被dp[i][j-w[i]]继承过了
}    
memset(f,-0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
    for(int j=w[i];j<=m;j++)//一定要注意枚举的顺序！！！
        f[j]=max(f[j],f[j-w[i]]+v[i]);
复杂度:O(n*m)

当面对随机数据时，完全背包可以先贪心筛除掉一些不必要的物品（体积相同选价值最大；体积更大，价值更小，直接舍弃），可以极大增加时间效率。

多重背包

问题模型：对每一个物品，最多能用t[i]次。

暴力的方法：直接枚举这个物品用了多少次
二维写法:
memset(dp,-0x3f,sizeof(dp));
dp[0][0];
for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
        dp[i][j]=dp[i-1][j];
        for(int k=1;k<=t[i]&&k*w[i]<=j;k++)
            dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]);
    }
一维写法:
memset(f,-0x3f,sizeof(f))l
f[0]=0;
for(int i=1;i<=n;i++)
    for(int j=m;j>=0;j--)
        for(int k=1;k<=t[i]&&k*w[i]<=j;k++)
            f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);
复杂度:O(n*m*t[i])

优化一:二进制拆分原理
将t[i]个物品拆成1+2+4+8…2^k+x, 这样k+1组，x小于2^(k+1) ，然后我们会发现这些组能拼成0…t[i]每一种情况，然后这样我们就成了n*log(t[i])个物品的0/1背包问题。            对于[0,2^(k+1)-1]都能拼成，所以[x,2^(k+1)-1+x]也都能拼成，x<=2^(k+1)-1， 则[0,2^(k+1)-1+x]全能拼成。
复杂度:O(n*m*log(t[i]))
优化二:单调队列优化
理解起来难度较大，我看了好久才看懂（假装看懂）
我们先观察一下二维的dp方程
dp[i-1][j-k*w[i]]+k*v[i]
我们发现对于第二维，我们的j和能转移过来的j-w[i]*k在模w[i]意义下是同余的，也就是说我们可以对于第二维按照模w[i]进行分类，不同类之间不会互相影响
设f[j]=dp[i-1][j*w[i]+r]。r是我们枚举模w[i]的一个类
dp[i][j*w[i]+r]=max(f[k]+(j-k)*v[i]);j-k<=t[i]
我们把式子转化一下
dp[i][j*w[i]+r]=max(f[k]+k*v[i])+j*v[i];j-k<=t[i]
实际上就是一个滑动窗口取最值的问题，直接单调队列优化即可
复杂度:O(n*m)

分组背包

◦一共有n组，每组有size[i]个物品，第i组第j个物品的费用为w[i][j]，价值

v[i][j]，每个组里的物品是互斥的，意味着你在一组物品中只能选择一个

物品，求花费小于等于m能得到的最大价值。

◦ Size之和小于等于1000，m<=1000

区别不大。
memset(f,-0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
    for(int j=m;j>=0;j--)
        for(int k=1;k<=size[i]&&w[i][k]<=j;k++)
            f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);

二维背包问题

都差不多，只是多了一维而已（略）

背包问题的解题思路

对于一般的背包问题

◦做背包问题最关键的就是找清楚并反问自己？

◦这题里面什么是容量？什么是物品？什么是物品的费用？什么是物品的价值？

◦容量，就是这题当中我们怎样表示状态的数组。

◦费用，就是用来f[i]---->f[i+v[k]]，状态转移的跨度。

◦价值，就是你这个dp的数组，所维护的东西。维护的数值！

◦背包dp一定要理解好这三点，因为很多时候题目中的“费用”并非背包dp中的“费用”