题解 P1048 【采药】

2018-08-18 18:20:52


这是道背包动规的模板题。

基础(已经了解的可以跳过)

首先,什么是动规呢?

动态规划,简称动规,是递推的一种。
和递推差不多,一般通过双重循环,逐步推出结果。
需要注意的是,要通过动规推出结果,必须保证每一步的结果都不会影响到前面算好的结果,以致反复影响。

什么是背包问题?

背包问题是动规的经典题,大致分为简单背包,0/1背包,完全背包,多重背包等。这一题是0/1背包问题,也就是: 给你一个容量为t的背包和n件价值为v[i],体积为w[i]的物品(每件物品只能装一次),让你编程计算背包装下的物品价值最多是多少。

进入正题

讲了这么多,我们到底怎么求背包问题呢?

我学动规的时候被这个问题卡了很久,因为我不知道f[i]到底指的是什么,以至于完全看不懂别人讲的。
首先我们引入一个概念:设f[i]表示容量为i的背包能获得的价值最多是多少。那么,f[0]很明显是0,因为一件物品都装不下。而我们要求的就是当容量为t时可获得的最大价值,也就是f[t]。

然后我们如何求f[i]可获得的价值?

我们都知道,只有背包剩余的容量大于一件物品时,才能装得下这件物品,获得这件物品的价值。那么我们就可以从每件物品出发:

for(int i=1;i<=n;i++){

}

然后我们利用上面说的性质,枚举可以装得下第i件物品的剩余容量(f[i]):

for(int i=1;i<=n;i++){
    for(int j=t;j>=w[i];j--){ //t为背包总容量

    }
}

为什么要从t开始枚举呢?
因为我们的每个物品只能放一次,而f[j]要靠f[j-w[j]]的价值求出来,如果我们先枚举f[j]再枚举f[j]以后的内容,就会被f[j]影响到,也就相当于第i件物品放了两次或以上(这涉及到完全背包问题,需要了解的可以去百度一下,或者做一下P1616)。所以我们从t开始枚举,以免影响到之前的f[i]。

然后我们就可以通过动规的性质(不会影响到枚举过的内容)来求f[t]了。

由于不会影响到之前枚举过的内容,所以我们可以放心的贪心:

for(int i=1;i<=n;i++){
    for(int j=t;j>=w[i];j--){
        f[j]=max(f[j-w[i]]+v[i],f[j]); //w[i]是第i件物品的体积,v[i]是第i件物品的价值。
    }
}

由于每件物品只能放一次,所以只有两个选择:放和不放(这也是0/1背包名字的来源)。
不放的话,f[j]还是f[j],没有任何变化;
放的话,背包的容量就少了w[i],只能获得f[j-w[i]]+v[i]的价值。
这两者的最大值,就是我们要求的f[j]。
最后的答案就是容量为t时获得的最大价值,也就是f[t]。
代码如下:

#include<iostream>
#include<cmath>
using namespace std;
int f[1001],n,t,v[101],w[101];
int main(){
    cin>>t>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=t;j>=w[i];j--) {
            f[j]=max(f[j-w[i]]+v[i], f[j]);
        }
    }
    cout<<f[t];
    return 0;
}