背包问题总结

01背包

题目

有N件物品和一个容量为V的背包。第i件物品的费用是w[i],价值是v[i],求将哪些物品装入背包可使价值总和最大。

基本思路

主要特征:每个物品只有一件,只有放与不放两种状态,设dp[i][j]表示重量限制为j时在前i个物品中能得到的最大价值

\[dp[i][j] = max(dp[i-1][j],dp[i-1][j -w[i]] + v[i])\]

因为每个物品只有两种选择则第i个不选,最大价值为dp[i-1][j],第i个要选时就要为第i个物品腾出w[i]的空间,再加上v[i];

可以发现前i个的状态都是由前i-1个推来,则可以用滚动数组滚动一维

一维情况第二层倒序枚举原因:因为是一维,正序枚举会把第i层更新的值覆盖上去,而之后又傻乎乎把被覆盖的值当做第i-1的值使用(其实也就是第i个物品可能被多次选用,完全背包将要用到)

inline void _01beibao()
{
    for(rint i=1;i<=n;i++)
        for(rint j=m;j>=wi[i];j--)
            dp[j]=max(dp[j],dp[j-wi[i]]+vi[i]);
}

求01背包第k大

inline void _01kth()
{
    for(rint i=1;i<=n;i++)
    {
        for(rint j=m;j>=wi[i];j--)
        {
            int c1=1,c2=1,cnt=0;
            while(cnt<=k)
            {
                if(dp[j][c1]>dp[j-wi[i]][c2]+vi[i]) gg[++cnt]=dp[j][c1++];
                else gg[++cnt]=dp[j-wi[i]][c2++]+vi[i];
            }
            for(rint cc=1;cc<=k;cc++) dp[j][cc]=gg[cc];
              //这里dp[j][k],表示第i层价值为j时的前k大值,显然dp[i][v][1..K]这K个数是由大到小排列的,所以我们把它认为是一个有序队列。
              //然后原方程就可以解释为:dp[i][v]这个有序队列是由dp[i-1][v]和dp[i-1][v-c[i]]+w[i]这两个有序队列合并得到的。
            }
    }
}

完全背包

题目

有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

基本思路

基本特点:每个物品有无数件,状态是取0-V/w[i]件。dp[i][j]定义同上,有

\[dp[i][j] = max(dp[i][j],dp[i-1][j-k \times w[i]] + k \times v[i])\]

由于可以多次选取,正序枚举可以利用之前被w[i]更新的dp值(本质就是多次选择),也因此可滚动一维。

inline void wanquanbeibao()
{
    for(rint i=1;i<=n;i++)
        for(rint j=wi[i];j<=m;j++)
        dp[j]=max(dp[j],dp[j-wi[i]]+vi[i]);
}

多重背包

混合背包

二维费用背包

分组背包

有依赖的背包

注意

“最多”与“恰好”

推荐博客
背包九讲原文
干脆背包九讲.pdf

上一篇:中文转换成html中的utf-8


下一篇:AGC037C Numbers on a Circle【构造】