对于这道题目首先是要看懂题目,对吧....之前做题目一直是百度的，现在也是这样（有点废话了）。
但是，首先我先解释下题目的大意吧。
问题描述
新学期就要到了，多多明天就要回学校上课了。因为到学校后就十分的忙了，所以呢，她决定happy，happy。 她十分喜欢看动画片。所以她想要她的舅舅给她买些动画片和她一起看。她的爷爷给她们L分钟看动画片。之后呢，她们就必须得去睡觉了。
多多列出了N部电影。这些都是她的最爱，她想要她的舅舅买给她。她呢，也给出了这些电影每一部的价值，Vi（可以是V1、V2、V3........Vi）。她喜欢贵点的（我也喜欢贵点的）。每部电影需要Ti的时间来播放。如果多多选择了这部电影看了，就一定要把它看完的。
但是这里有个奇怪的问题，这个商店只卖M部电影（不多也不少），这个对她的舅舅来说有点困难。到底如何来选择这M部电影呢？？？这个舅舅有点笨，你来帮帮他。
输入
第一行呢是t（1<= t <= 10），这个是测试用例的数字。
接下来连输三个数字N（N <= 100）、M（M <= N）、L（L <= 1000）。
N：多多要买的电影数。
M：商店能卖得电影数。
L：最长能看多长时间。
接下来的N行中，每行两个数字，第一个是电影的时长，第二个是价值。
输出
多多获得获得最多的快乐值。
这是个背包问题，首先我们谈谈对背包问题的理解。（介意去看看背包九讲）
首先是01背包问题，其具体思路为F[i，v] = max{F[i-1，v]，F[i-1，v-Ci] + Wi}。
完全背包问题，具体思路为F[i，v] = max{F[i-1，v-kCi] + kWi | 0<=kCi<=v}。
多重背包问题，思路为F[i，v] = max{F[i-1,v-k*Ci] + k*Wi | 0 <= k <= Mi}。
额...刚才看了部电影，《决胜21点》，大家有兴趣可以去看看。
好，继续正题哈。此题的关键是F[i，v] = max{F[i-1，v]，F[i-1，v-Ci] + Wi}这个好像有点像0-1背包。好吧，贴代码了。
1 #include2 #include 3 #include 4 using namespace std; 5 int c[101], w[101]; 6 int dp[101][1001]; 7 int main(){ 8 9 int t;10 scanf("%d", &t);11 while (t--){12 int n, m, l;13 scanf("%d%d%d", &n, &m, &l);14 int i, j, k;15 for (i = 0; i < n; i++)16 scanf("%d%d", &c[i], &w[i]);17 memset(dp, -1, sizeof(dp));18 dp[0][0] = 0;19 for (i = 0; i < n; i++){20 for (k = m; k > 0; k--){21 for (j = l; j >= c[i]; j--){22 if (dp[k-1][j-c[i]] != -1 && dp[k][j] < dp[k-1][j-c[i]] + w[i])23 dp[k][j] = dp[k-1][j-c[i]] + w[i];24 }25 }26 }27 int ms = 0;28 for (i = l; i >= 0; i--)29 if (dp[m][i] > ms)30 ms = dp[m][i];31 printf("%d\n", ms);32 }33 return 0;34 }