标签：NOIP2005

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 ] )

]]>