初学DP(3.5) – 完全背包 – Luogu P1616 疯狂的采药

完全背包 我们先来回顾一下 01 背包

针对于有一定空间,一定数量的物品,每个物品只能放一个,我们可以把他当为 01 背包,它的状态转移方程是:
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
那么什么是完全背包呢? 针对于有一定空间,一定数量的物品,每个物品能放无数个的背包,我们称其为完全背包, 我们曾经在 初学DP (1) – 01 背包 – 装箱问题 & NOIP 2005 普及 第三题 采药 中提到过 01 背包的 j 循环 这层循环如果从小到大,你们他就会按个累加,那么也就是说把 j 循环从小到大,它,就变成了完全背包

疯狂的采药

这道题中他很明显的说了他和采药的不同点:
1.每种草药可以无限制地疯狂采摘。 2.药的种类眼花缭乱,采药时间好长好长啊!师傅等得菊花都谢了!
那tm不久是完全背包吗!!!!!! 所以你把采药的 j 循环倒一下,数组开大点,AC!!! ]]>

初学DP (1) – 01 背包 – 装箱问题 & NOIP 2005 普及 第三题 采药

DP

动态规划
我们知道,贪心的方法是取全局最优解,而 DP 是指通过解决局部最优解,来找到整个问题的最优解,我们来用看看下面这个求最短路的例子:
    / 2 \
1 - 3   - 5
   \ 4   /
我们求从 1 到 5 的的最短路,首先我们应该求出 1->2/3/4 的最短路,我们已经知道了 f(1) ( 1 的最短路)=1,将其移动到并算出 1->2 的最短路的过程就叫状态转移,而 f(1) 就是所谓的状态。 另外我们知道2/3/4 是同一层的东西,所以我们称这几个叫做”阶段”,1 也是一个阶段。 另外再来说说DP,需要满足的一些条件
  • 无后效性
  • 最优子结构
最优子结构是指”每个阶段的最优状态可以从之前某个阶段的某个或某些状态得到” 而无后效性是指”前面得到的解,对后面没有影响”

装箱问题

题目链接: [http://codevs.cn/problem/1014/] 首先我们第一个想到的是贪心,不过你尽管贪,能 A 算我输 我们先看代码吧qwq
#include <stdio.h>
int n,v;
int a[40],f[40][210000];
int main(){
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=v;j>=a[i];j--){
            if(f[i-1][j-a[i]]+a[i]>f[i-1][j]) f[i][j]=f[i-1][j-a[i]]+a[i];
            else f[i][j]=f[i-1][j];
        }
        for(int j=1;j<a[i];j++) f[i][j]=f[i-1][j];
    }
    printf("%d",v-f[n][v]);
}
a[] 价格 f[i][j] 当第 i 个物品被放进来时,容量为 j 的箱子最多可以放多少. 所以我们可以很容易得到下面这个状态转移方程
f[i][j]=max( f [ i-1] [ j – a [ i ] ] + a [ i ] , f [ i – 1 ] [ j ] )
将这个方程输入进程序,你的第一道dp就完成了

循环 j ?


for(int j=v;j>=a[i];j–)
为什么 j 要倒着来?他能正这来吗? 当然是不能 如果你有心情手推你会发现,它正着来的时候会累加qwq 没错这就是完全背包,有关完全背包,我们过几次就会讲了

采药

题目链接: [https://www.luogu.org/problemnew/show/P1048] 不止这一家有这道题的说~
对比一下上面的装箱问题,我们可以发现,他们很相似,不过采药比装箱多以一个项目 – 时间 但是这显然不打扰,把 j 对应改成时间就行了 不过再让我们看看,这个二维数组,到底有没有必要
f[i][j]=max( f [ i-1] [ j – a [ i ] ] + a [ i ] , f [ i – 1 ] [ j ] )
我们只用到了 i-1 !!! 所以我们可以把方程化成下面这个
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
#include <cstdio>
using namespace std;
int t,m;
int time[110],pri[110],f[1100];
int main(){
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++) scanf("%d%d",&time[i],&pri[i]);
    for(int i=1;i<=m;i++){
        for(int j=t;j>=time[i];j--){
            if(f[j]<f[ j-time[i] ]+pri[i]){
                f[j]=f[ j-time[i] ]+pri[i];
            }
        }
    }
    printf("%d",f[t]);
}

01背包

说了这么多,让我们总结一下 01 背包 这种类型 针对于有一定空间,一定数量的物品,每个物品只能放一个,我们可以把他当为 01 背包,它的状态转移方程是:
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
]]>