动态规划背包算法（01背包和完全背包）

时间：2022-06-17 18:42:31

定义

给你一堆物品，每个物品有体积和价值，求一定体积下的最大价值和。

（手动分割）

01背包

这类题目特点是每个物品只有1个。
例题
NOIP2005普及组 采药
题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入输出格式

输入格式：
输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式：
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例

输入样例：
70 3
71 100
69 1
1 2

输出样例：
3

（手动开始）
这玩意是个01背包裸题。时间是体积，价值就是价值。
首先我们先想

暴力！！！

李J说过

暴力出奇迹！那些考场上一开始就想标算的大多都死在路上了。

每一个物品只有用或者不用两种选择。我们只需枚举每个物品的两种状态，暴力搜索即可。时间复杂度 O(2n) 。
显然爆炸。
不过有一些特殊的题目需要这种方法。oi是需要开阔的思维的。这种算法它的复杂度只与物品的个数有关，于是，当你发现，题目中物品的个数较小时，你可以尝试这个玩意。

那么我们需要进一步优化。
我们发现我们可以用F(i,j)表示前i个物品用了j个空间的最大价值和。
这样，我们可以用一个式子表示递推过程。

F(i,j)=max(F(i−1,j),F(i−1,j−vi)+wi)

显然对不对？
时间复杂度 O(nm) 。
代码如下 

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,f[105][1005],w[105],v[105];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(v[i]>j)f[i][j]=f[i-1][j];
            else{
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            }
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

其实还有优化，优化空间。
我们发现，f(i)这一行只与f(i-1)一行有关。那么我们可以用循环数组直接更新，省掉一维空间。
式子就变成了这样

F(j)=max(F(j),F(j−vi)+wi)

因为我们需要使F(j)在F(j-vi)之前更新，所以j的循环是 从大到小。
代码如下 

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,f[1005],w[105],v[105];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    printf("%d",f[m]);
    return 0;
}

01背包是背包问题中最最最基础的了。你可以手动模拟一发，这非常有利于你理解这个问题。

完全背包

相比01背包，这玩意就是每个物品都能取无限个。
例题疯狂的采药
嘛，随便想想就行了。
首先还是先想暴力。
直接把每个物品复制 m/v[i] (上取整)份，跑01背包就行了。
时间复杂度 O(n∗m∗乱七八糟) 。

显然这有时候是不能被接受的，我们想让它变成01背包一样的复制度。其实很简单。
我们继续用F(i,j)表示前i个物品j个空间，那么转移方程就成了这个样子。

F(i,j)=max(F(i−1,j),F(i,j−vi)+wi)

即，不变，或者再放进去一个物品i。
是不是和01背包的转移方程很像。
同样可以用滚动数组优化。就是j的顺序为从小到大。
代码如下 

#include<cstdio>
#include<iostream>
int n,m,f[100005],w[10005],v[10005];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=m;j++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    printf("%d",f[m]);
    return 0;
}

多重背包

多重背包就是每个物品有最多取的个数。
首先暴力
对于每个物品把物品都列出来，跑01结束。
时间复杂度 O(n∗m∗k) 。

对于多重背包我们有两个优化，二进制拆分和单调队列优化。
本篇先不讲了

题目推荐
NOIP2006提高组 金明的预算方案
感谢观看！
by 星戬

标签：

相关文章