DP之动态规划

2019/01/10 09:17
阅读数 6

动态规划DP有着很高的上限,难的DP所要写的转移方程往往很难想想到,下面博主简单介绍一下基础的DP
首先便是大家熟知 但对于初学者又比较困难的背包问题

这里简单介绍一下01背包

杭电2602

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1006];
int b[1006];
int dp[1006][1006];
int n,m;
int t;
int main() {
    scanf("%d",&t);
    while(t--) {//多组输入
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));//多组输入的初始化!
        int i,j;
        for (i=1; i<=n; i++)
            scanf("%d",&a[i]);
        for (j=1; j<=n; j++)
            scanf("%d",&b[j]);//输入

//        for (i=1;i<=n;i++)
//        printf("%d",a[i]);
//    for (j=1;j<=n;j++)
//        printf("%d",b[i]);
        for (i=1; i<=n; i++) {
            for (j=0; j<=m; j++) {
                if (j>=b[i])
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-b[i]]+a[i]);//转移方程 动态规划的核心
                else
                    dp[i][j]=dp[i-1][j];
            }
        }//重点解释
//    for (i=1; i<=n; i++)
//        for (j=1; j<=m; j++) {
//            if (j==m)
//                printf("%d\n",dp[i][j]);
//            else
//                printf("%d ",dp[i][j]);
//        }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}

看到这里很多萌新就要问了,我还是看不懂怎么办

下面博主就对代码中的重要部分解释。

我们定义一个二维数组DP[i][j];

其中i表示第i个物品 ,j表示当前所需的容量 而DP[i][j]的值就是当前背包所装物品的总价值

那我们需要怎样实现转移呢

如题目样例 

1
5 10
1 2 3 4 5
5 4 3 2 1
我们从第一个物品开始
选择放入和不放入 (在这里有萌新要问了,怎么不放入呢)
ps:其实很简单 比如第一个物品 重5价值1;我们在背包中,背包容量小于5的是放不下的,这其实就代表着放和不放,因为第一个物品放入之后是优先在刚好适合的位置放入的,并不会影响下一个的放入
上图:

 

比如 第一个物品的放入 只能在背包容量大于5

而第二个物品的放入能在大于4,对于第二个物品,如果想在放入第一个物品之后放第二个物品  则需要从背包中空出第二个物品的容量  所以就只能选用既能放下第一个又能放下第二个的背包

(背包容量为9的背包可以放入大小为5 和大小为4 的物品 容量为10 的当然也可以)

而那些容量小于4的就是没有放入第二个物品

同样的对于第三个物品 要从能放入第三个物品的容量大小的背包开始放入 以此类推。

这样我们便可以做到对于每个物品选择放入和不放入  放入的话便从最小所需容量开始放入 

于是我们便能退出转移方程 对于第i个物品 如果我们想要放入 那么dp[i][j]=dp[i-1][j-a[i]]+b[i];

dp[i-1][j-a[i]]便是上一个能放入第i个物品背包 在此背包中放入第i个物品 ,然后所包含的价值加上第i个物品的价值;

转移方程写出来了 题目就很简单了

博主对于DP的理解是 ,DP是一种很高级记忆化搜索 ,高级到什么程度呢,高级每搜一步,就需要将搜索的结果储存到DP数组中,然后利用搜索的结果进行下一次搜索 然后继续储存。

是不是很高级呢?

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部