问题 A: 【动态规划】采药_二维数组_一维数组

问题 A: 【动态规划】采药

时间限制: 1 Sec  内存限制: 64 MB
提交: 35  解决: 15
[提交][状态][讨论版]

题目描述

山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值，在一段时间内如何让采到的草药价值最大。

输入

第一行有两个用空格隔开的整数T和M（1≤T，M≤100），T代表总共采药时间，M代表草药数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某种草药的时间和这株草药的价值。

输出

只包含一个整数，表示在规定的时间内可以采到的草药的最大总价值。

样例输入

70 3

71 100

69 1

1 2

样例输出

3

解题思路：实际就是01背包，用二维数组的时候注意：需要考虑j<t[i]的情况，因为后面会有用到dp[i-1][j-t[i]] (j<t[i])的情况。
　　所以还是学着用一维数组做01背包吧，既节省空间有不用考虑这么多情况。
代码：二维数组：

#include<cstdio>

#include <iostream>

#include <cstring>

using namespace std;

int dp[][];

int main(){

    int T;

    int M;

    int maxx=;

    int t[];

    int p[];

    while(scanf("%d %d",&T,&M)!=EOF){

        maxx=;

        memset(dp,,sizeof(dp));

        for(int i=;i<=M;i++){

            scanf("%d %d",&t[i],&p[i]);

        }

        for(int i=;i<=M;i++){

            for(int j=;j<=T;j++){

                if(j>=t[i]){

                    dp[i][j]=max(dp[i-][j],dp[i-][j-t[i]]+p[i]);

                }else{

                    dp[i][j]=dp[i-][j];

                }

            }

        }

        printf("%d\n",dp[M][T]);

    }

    return ;

}

一维数组：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int a[]={};

 int t[]={};

 int p[]={};

 void zeroonepack(int T,int t,int p){

     for(int i=T;i>=t;i--){

         a[i]=max(a[i],a[i-t]+p);

     }

 }

 int main()

 {

     int T,M;

     while(scanf("%d %d",&T,&M)!=EOF){

         memset(a,,sizeof(a));

         for(int i=;i<M;i++){

            scanf("%d %d",&t[i],&p[i]);

         }

         for(int i=;i<M;i++){

             zeroonepack(T,t[i],p[i]);

         }

         printf("%d\n",a[T]);

     }

     return ;

 }

问题 A: 【动态规划】采药_二维数组_一维数组的相关教程结束。