dp之二维背包hdu3496

题意：给你n张电影门票，但一次只可以买m张，并且你最多可以看L分钟，接下来是n场电影，每一场电影a分钟，b价值，要求恰好看m场电影所得到的最大价值，要是看不到m场电影，输出0；

思路：这个题目可以很明显的看出来，有两个限制条件，必须看m场电影的最大价值........其实我前面在01背包时提过，对于这样的条件，要可以看第n场电影，那么相对应的第n-1场电影必须看了，否则不能进行动态转移.......我的想法是，0代表着这场电影没有看，>0代表这场电影看了。其他的就是动态转移了，很容易得到，dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+val[i])........当然，在最开始的dp[0][0]=1，那么得到的最大值会在第m场电影里面，最大值需要减去初始值........也就是1

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

int dp[105][1005],s[105][2];

int max(int x,int y)

{

    if(x>y)

    return x;

    else

    return y;

}

int main()

{

    int text;

    scanf("%d",&text);

    while(text--)

    {

        int N,M,L;

        scanf("%d %d %d",&N,&M,&L);

        for(int i=1;i<=N;i++)

        scanf("%d %d",&s[i][0],&s[i][1]);

        memset(dp,0,sizeof(dp));

        dp[0][0]=1;

        for(int i=1;i<=N;i++)

        {

            for(int j=M;j>=0;j--)

            {

                for(int k=L;k>=0;k--)

                {

                    if(k>=s[i][0]&&j>0&&dp[j-1][k-s[i][0]]&&dp[j][k]<dp[j-1][k-s[i][0]]+s[i][1])

                    {

                        dp[j][k]=dp[j-1][k-s[i][0]]+s[i][1];

                    }

                }

            }

        }

        int i,maxn=0;

        for(i=0;i<=L;i++)

        if(dp[M][i]>maxn)

        maxn=dp[M][i];

        if(maxn==0)

        printf("0\n");

        else

        printf("%d\n",maxn-1);

    }

    return 0;

}

巴特西

dp之二维背包hdu3496

最新文章

热门文章