题目链接: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);
......
阅读全文