暑假练习：uva12563（01背包问题）

原题链接：uva12563

解析：

        这题我花了十几分钟就敲出来了，但是没通过，于是改了俩个多小时才发现少打了max....。

        这题是典型的01背包问题，其中时间可以看作背包容量，每首歌就可以看作体积了，那么重量就是1。本题要求唱最多的歌的同时要尽可能唱的时间久一点。那d（i，j）表示在前i首歌中，剩余时间为t时的最多唱歌数。但是要注意的是，题目还要求输出唱歌的时间，这样就不能简单的对每个符合条件的d（i，j）赋值了，要加一下约束：

• 初始化d所有值为-1，令d[i][0]为0（每一行第一个元素）
• 如果d(i-1,j-songTime[i]) > 0则进行状态转移。这样做的目的时为了不浪费每一秒的时间，将所有时间都用来唱歌，如果浪费了时间，则将其值设为-1。这样就可以通过j的值来找最久唱歌时间了。

代码实例：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int c = 180*50+678+5;
int main()
{
int loop;
cin >> loop;
int kase = 0;
while(loop--){
int n,t;
cin >> n >> t;
int songTime[n+1];
for(int i = 1;i <= n;i++)	cin >> songTime[i];
int d[n+1][c];
int ans = 0;
memset(d,-1,sizeof(d));
for(int i = 0;i <= n;i++)	d[i][0] = 0;
for(int i = 1;i <= n;i++)
for(int j = 0;j < t;j++){
d[i][j] = d[i-1][j];
if(j >= songTime[i] && d[i-1][j-songTime[i]] >= 0){
d[i][j] = max(d[i][j] , d[i-1][j-songTime[i]]+1);
ans = max(d[i][j],ans);
//	cout << i << " " << j << " " << ans << " " << d[i][j]<<endl;
}
}
for(int i = t;i >= 0;i--)
if(d[n][i] == ans){
printf("Case %d: %d %dn", ++kase, ans + 1, i + 678);
break;
}
}
}