学步园

题目链接：Click here~~

题意：

有n个电影，每个电影有时间c和价值w两种属性，从中选m个，且必须是m个，使时间不超过T且价值最大。

解题思路：

挺裸的二维01背包，只是有一维要装满，标记下即可。

状态转移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-c]+w).( i 表示电影个数， j 表示时间)

初始时将dp[0][j]都设为0，其他都设为-1。-1表示不能装满。

#include <stdio.h>
#include <string.h>
#define max(a,b) a > b ? a : b
int dp[103][1003];
int main()
{
    int z,n,m,c,w,T;
    scanf("%d",&z);
    while(z--)
    {
        memset(dp,-1,sizeof(dp));
        memset(dp[0],0,sizeof(dp[0]));
        scanf("%d%d%d",&n,&m,&T);
        for(int k=1;k<=n;k++)
        {
            scanf("%d%d",&c,&w);
            for(int i=m;i>=1;i--)
                for(int j=T;j>=c;j--)
                    if(dp[i-1][j-c] != -1)
                        dp[i][j] = max(dp[i][j],dp[i-1][j-c]+w);
        }
        if(dp[m][T] < 0)
            puts("0");
        else
            printf("%d\n",dp[m][T]);
    }
    return 0;
}