[数据结构与算法]背包小记（01，完全，多重分组）

背包小记

01背包

概述：

给你 $n$ 个物品，每个物品的价值为 $w_i$ ,现在给你一个$m$容量的背包 ， 每个物品可以选择要或者不要，问在背包容量下最大物品价值

状态方程

二维状态方程：$dp[i][j]=max(dp[i?1][j],dp[i?1][j?v[i]]+w[i])$
**一维状态方程：$dp[j]=max(dp[j],dp[j?v[i]]+w[i])(for(intj=m;j>=v[i];j??))$ **

完全背包

概述：

每个物品无限个，其他条件与01背包相同

状态转移方程

二维状态方程：
$dp[i][j]=max(dp[i?1][j],dp[i][j?v[i]]+w[i])$
$dp[i][j]=max(dp[i?1][j],dp[i?1][j?v[i]]+w[i],....,dp[i?1][j?k?v[i]]+w[i]?k)$
$dp[i][j?v]=max(dp[i?1][j?v],dp[i?1][j?2?v[i]]+w[i],....,dp[i?1][j?k?v[i]]+w[i]?k)$

**一维状态方程：
$dp[j]=max(dp[j],dp[j?v[i]]+w[i])(for(intj=v[i];j<=m;j++)$
**

多重背包

概述：

物品数量分别为 $s_i$ , 其他与01背包相同

解法1：

将每个物品的数量用二进制表示法进行拆分，最后得到cnt个物品，再采用01背包选则即可，状态转移方程和01背包相同

解法2（单调队列优化）：

由完全背包的状态转移方程$dp[i][j]=max(dp[i?1][j],dp[i?1][j?v[i]]+w,....,dp[i?1][j?k?v[i]]+w?k)$可得，可将对0-m对v[i]取余将其划分为v[i]个类，对于每个类用单调队列维护即可，每次入队的数实际为 $dp[j+k?v]?k?w$

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010;
int dp[N],q[N],pre[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0 ; i < n ; i ++){
        int v,w,s;
        cin>>v>>w>>s;
        memcpy(pre,dp,sizeof dp);
        
        for(int j = 0 ; j < v ; j ++){//v个划分
            int head = 0 , tail = -1;
            for(int k = j ; k <= m ; k += v){
                
                if(head <= tail && k - s*v > q[head]) ++ head;
                
                while(head <= tail && pre[q[tail]] - (q[tail] - j)/v * w <= pre[k] - (k - j)/v * w ) -- tail;
                
                if(head <= tail) dp[k] = max(dp[k] , pre[q[head]] + (k - q[head])/v * w);
                
                q[++tail] = k;
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

分组背包：

概述：n组物品，每组由$s_i$个，每组只能取一个，其余和01背包相同

解法：01背包里面每次枚举第i组物品中的$s_i$个物品

状态方程

一维状态方程：$dp[j]=max(dp[j],dp[j?s[k]]+w[k])$