无限UCW

动态规划之背包问题专题(Ⅰ)
背包问题是动态规划中一类基础而重要的问题,它体现了动态规划的基本思想和妙处,同时也是对思维的一个挑战~Part.1...
扫描右侧二维码阅读全文
03
2019/02

动态规划之背包问题专题(Ⅰ)

背包问题是动态规划中一类基础而重要的问题,它体现了动态规划的基本思想和妙处,同时也是对思维的一个挑战~
Part.1 Including 01背包,完全背包&多重背包 和 混合背包问题。



概念解说:

  • 背包:装物品的容器,广泛的抽象概念。
  • 状态:简单理解为描述问题的阶段。
  • 状态转移方程:由已知状态递推描述未知状态的计算原理。

01背包问题

问题特征:每种物品只有一件,可以选择装或不装。

这是背包问题中最基本的一类,也是所有背包的基础,其他背包问题可以转化为01背包来求解。

例题:采药(P1048 in LuoguOJ

题目描述

输入输出格式

输入格式:
第一行有$2$个整数$T(1 \leq T \leq 1000)$和$M(1 \leq M \leq 100)$,用一个空格隔开,$T$代表总共能够用来采药的时间,$M$代表山洞里的草药的数目。
接下来的$M$行每行包括两个在$1$到$100$之间(包括$1$和$100$)的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出格式:
$1$个整数,表示在规定的时间内可以采到的草药的最大总价值。

输入输出样例

输入样例:

70 3
71 100
69 1
1 2

输出样例:

3

说明

对于$30\%$的数据,$M \leq 10$;
对于全部的数据,$M \leq 100$。
NOIP2005普及组第三题。

分析与题解

分析

每种草药只有一株,且草药具有时间和价值两个属性,是典型的01背包问题。
题目要求“在规定的时间内”,故时间(即背包)不必保证全部用完(装满),设f[i][t]表示将$i$个物品装入容量为$t$的背包中所能获得的最大价值,初始化令for(int k=0;k<=T;k++)f[0][k]=0;。则状态转移方程为:
f[i][j]=max{f[i-1][j],f[i-1][j-t[i]]+v[i]}
其中t[i]表示采集第$i$种草药所花费的时间,v[i]表示第$i$种草药的价值。j-t[i]恒大于等于零(将用循环边界进行限定)。
编程时使用滚动数组优化空间复杂度,需注意更新的顺序。由于t[i]大于零,j-t[i]一定是比j小的,故从后向前更新避免覆盖。应用滚动数组的理论依据是第$i$次计算的值只与第$(i-1)$次有关,此时由于上次计算的结果保存在数组f中,故可以直接进行下次计算。
01背包问题的滚动数组示意图:
01背包问题的滚动数组示意图

由于更新f数组即“红色向黄色区域推进”这一过程计算所需要的数值在蓝色区域内保存,所以此时f数组的对应位置保存的数据并没有被覆盖,仍是上次计算后的值,所以只需要改变计算顺序就可以只使用一维数组来进行递推。
注意,虽然上图呈现了“似乎两个数组”,但实际上f数组中只保存蓝色部分和红色部分的对应数据,黄色和灰色部分均不是实际存在的。

滚动数组优化虽然可以大幅减小空间复杂度,但对于解的打印则更为困难,若题目需要打印解,则应当慎用。

《算法竞赛入门经典》对于此类问题的解法也有较为详细且易懂的讨论,可作为参考。

AC代码及附注

R15865087
需要注意的是关于空间复杂度的一个常数优化,观察优化后的状态转移方程可以发现,本题可以边读边处理,因为每种草药的计算只与当前草药的时间t价值v有关,而不需要关心别的草药的情况,所以不需要特意把tv存成数组。

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXT = 1003;
int f[MAXT];
inline int max(int a,int b){
    return a>b?a:b;
}
int main(){
    int T,M;
    memset(f,0,sizeof(f));
    scanf("%d%d",&T,&M);
    for(int i=1;i<=M;i++){
        int t,v;//边读边处理 
        scanf("%d%d",&t,&v);
        for(int j=T;j>=t;j--){
            f[j]=max(f[j],f[j-t]+v);//状态转移方程,选择取或不取 
        }
    }
    printf("%d",f[T]);//输出最终结果 
    return 0;
}

归纳与体会

这类背包问题是背包中的基础,虽然基本但不简单,动态规划的思维难度和妙处初现。
上面还没有说到对于背包容量计算的常数优化,参考上面代码,即第二重循环为什么只到t为止。考虑计算的过程和j的实际意义,j代表当前计算的这个背包的容量,一方面,当j更小时j-t值为负无意义,另一方面,j小于t时这个物品一定放不进背包,根本无需选择,相当于直接进行f[j]=f[j]的计算,可以不写。
动态规划中一个很重要的思想就是子问题、子状态,例如上面的01背包问题,你以为只有一个背包?其实我们处理的是容量为 0,1,2,...,V 的所有背包,其中V表示最大容量。为什么动态规划解决背包问题这么有效?答案是它通过递推,用最初的显而易见的“把0个物品放入任意容量背包中所得的最大价值一定为0”的公理将后续复杂的无法一眼看穿的状态一步步表出,这正是这个算法的迷人之处。


完全背包问题

问题特征:对于一个容量有限的背包,每种物品都有无穷多个,不限制每种物品怎么装。

这是稍微进阶版的背包问题,个人体会不是特别难,但很有启发性。我通过对这种问题初始状态的学习可以说是稍稍窥见了动态规划 (dp) 状态设计的精妙之处。

例题:疯狂的采药(P1616 in LuoguOJ

题目描述

输入输出格式

输入格式:
输入第一行有两个整数$T(1 \leq T \leq 100000)$和$M(1 \leq M \leq 10000)$,用一个空格隔开,$T$代表总共能够用来采药的时间,$M$代表山洞里的草药的数目。接下来的$M$行每行包括两个在$1$到$10000$之间(包括$1$和$10000$)的整数,分别表示采摘某种草药的时间和这种草药的价值。
输出格式:
输出一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。

输入输出样例

输入样例:

70 3
71 100
69 1
1 2

输出样例:

140

说明

对于$30\%$的数据,$M \leq 1000$;
对于全部的数据,$M \leq 10000$且$M \times T < 10^{7}$。

分析与题解

分析

有了上面01背包的基础,本题显得简单多了,只需要改变循环的顺序即可(R16037903)。
简单看看改变顺序后的代码:

for(int i=1;i<=M;i++){
    int t,v;
    scanf("%d%d",&t,&v);
    for(int j=t;j<=T;j++){
        f[j]=max(f[j],f[j-t]+v);
    }
}

时间复杂度$O(MT)$,空间复杂度$O(T)$。

AC代码及附注

R16037903
仍然边读边计算,而且状态还是可以压到一维,弄懂01背包之后本题异常简单~

#include<bits/stdc++.h>
using namespace std;
const int MAXT = 100007;
int f[MAXT];
int main(){
    memset(f,0,sizeof(f));
    int T,M;
    scanf("%d%d",&T,&M);
    for(int i=1;i<=M;i++){
        int t,v;
        scanf("%d%d",&t,&v);
        for(int j=t;j<=T;j++){
            f[j]=max(f[j],f[j-t]+v);
        }
    }
    printf("%d",f[T]);
    return 0;
}

归纳与体会

完全背包也是较为基础的背包问题,直接转为01背包即可。
PS:完全背包问题还有一种解决的思路是选择“拿几件物品”而不是拆分,但优化后实质相同,改变计算顺序就是对物品的拆分,也可理解为选择多少件。

行间:上述两个题目均没有涉及“背包需要恰好装满”这样的特殊条件,当题目要求背包必须恰好装满时,可以在初始化上下功夫:f[0]初始化为0,其余全部置为负无穷(-INF)。这样操作是因为容量为0的背包初始时恰好装满,其余均不合法,直接用最小值卡掉,保证最终的解转移到的状态(请仔细反复阅读理解)为背包恰好装满。但你如果一定要写特判,就不存在这个问题了。


多重背包问题

问题特征:每个物品有件数上限。

进阶版的背包问题。

例题:宝物筛选(P1776 in LuoguOJ

题目描述

输入输出格式

输入格式:
第一行为一个整数$n$和$W$,分别表示宝物种数和采集车的最大载重。
接下来$n$行每行三个整数,其中第$i$行第一个数表示第$i$类物品价值,第二个整数表示一件该类物品的重量,第三个整数为该类物品数量。
输出格式:
输出仅一个整数$ans$,表示在采集车不超载的情况下收集的宝物的最大价值。

输入输出样例

输入样例:

4 20
3 9 3
5 9 1
9 4 2
8 1 3

输出样例:

47

说明

对于$30\%$的数据:$n \leq \sum{m_{i}} \leq 10^{4},0 \leq W \leq 10^{3}$。
对于$100\%$的数据:$n \leq \sum{m_{i}} \leq 10^{5},0 < W \leq 4 \times 10^{4},1 \leq n < 100$。
NOI导刊2010提高(02)。

分析与题解

分析

当单个物品取最大个数时若背包超载,则退化为完全背包问题,否则进行拆分。
拆分时可以考虑二进制思想,避免重复计算。
有前两种做铺垫,这一问题更加容易解决。
思路:如果单个物品全部拿完背包超载,则上界是废的,直接跑完全背包;若没有超载,则对物品进行拆分。
二进制拆分方法:对于一个正整数$n$,将其用$2^{k}$的形式表出,其中k依次0,1,2,3,...并取总和,特别注意,对于8这样的数,应当表示为8=1+2+4+1,因为必须保证拆分后不改变物品总个数,且小于物品总数的每一个正整数均必须存在方案能被表出(请反复阅读理解)。这是二进制的思想,$2^{k}$其实就是二进制下从右向左第$(k+1)$位为1,其余位为0的数。
伪代码:

while(N--){
    int v,w,n;
    scanf("%d%d%d",&v,&w,&n);
    if(w*n>=W){
        //完全背包
    }else{
        int k=1;
        while(k<n){
            int kv=k*v,kw=k*w;
            //kv,kw进行01背包
            n-=k;
            k=k<<1;
        }
        int nv=n*v,nw=n*w;
        //nv,nw再进行一次01背包扫尾
    }
}

这样就能轻松收掉了。看来2010年的NOI导刊也不过如此(废话),洛谷评级为蓝题(提高+/省选-)显然过难。时间复杂度为$O(W\sum{log n_{i}})$

AC代码及附注

R16045705
本题看起来就是前两题的一个混合版本吧,事实上马上我们将见到三者的混合版本,也将体现分开操作的思想。

#include<bits/stdc++.h>
using namespace std;
const int MAXW = 40007;
int f[MAXW];
int main(){
    memset(f,0,sizeof(f));
    int N,W;
    scanf("%d%d",&N,&W);
    while(N--){
        int v,w,n;
        scanf("%d%d%d",&v,&w,&n);
        if(w*n>=W){
            for(int j=w;j<=W;j++){
                f[j]=max(f[j],f[j-w]+v);
            }
        }else{
            int k=1;
            while(k<n){
                int kv=k*v,kw=k*w;
                for(int j=W;j>=kw;j--){
                    f[j]=max(f[j],f[j-kw]+kv);
                }
                n-=k;
                k=k<<1;
            }
            int nv=n*v,nw=n*w;
            for(int j=W;j>=nw;j--){
                f[j]=max(f[j],f[j-nw]+nv);
            }
        }
    }
    printf("%d",f[W]);
    return 0;
}

归纳与体会

多重背包体现转化思想,转成完全背包或01背包直接原地收掉。
But...后面这个拆分其实不是最优,仍然可以用单调队列优化。

Redo(拟)

考虑进行单调队列优化,将在之后篇目中进行讨论。优化后复杂度降至$O(WN)$,然而我还没学会,我太弱了……


混合背包问题

顾名思义,就是把上述三种混合起来,有的可以取1件,有的可以无限取,有的有件数上限。

思路:直接判断当前物品属于什么背包,就套对应的状态转移方程即可。


本篇文章到此为止,但关于背包问题的讨论还将继续。【to be continued...】

最后修改:2019 年 08 月 01 日 10 : 01 AM

发表评论