劲歌金曲
两层动态规划，需要满足在数量最多的情况下时间最长
第一层数量最多: 和01背包相似，状态d(i,j)是在面对第i首歌还剩j时间时所能唱的最多歌曲数，得出状态递推方程d(i,j)=max(d(i+1,j),d(i+1,j-len[i])),用递推法得出答案d(1,t)
第二层时间最多 :注意是在数量最多的情况下，递推方程和数量差不多
#include <iOStream>
using namespace std;
int d[101][100000]; //d(i,j)在面对第i首歌还剩j时间时所能唱的最多歌曲数int tt[101][10000]; //tt(i,j)在面对第i首歌还剩j时间时所能唱的最长时间（在歌曲数最多的情况下的最长时间）
int max1(int x,int y)
{
return x>y?x:y;
}
int main()
{
int m;
cin>>m;
int n,t;
int num=0;
while(m--)
{
num++;
cin>>n>>t;
int len[1001];
for(int i=1; i<=n; i++)
cin>>len[i];
for(int i=0; i<=t; i++) //初始化d[n+1][1...t]，用于递推第一层d[n][1...t]的赋值
{
int temp=n+1;
d[temp][i]=1;
tt[temp][i]=678;
}
for(int i=n; i>=1; i--)
for(int j=1; j<=t; j++)
{
int temp=j-len[i];
if(j>len[i])
{
d[i][j]=max1(d[i+1][j],d[i+1][temp]+1);
//在数量最大的情况下取最长时间
if(d[i+1][j]>d[i+1][temp]+1)tt[i][j]=tt[i+1][j];
else if(d[i+1][j]<d[i+1][temp]+1)
tt[i][j]=tt[i+1][temp]+len[i];
else //如果两种情况数量相等，取时间长的
tt[i][j]=max1(tt[i+1][j],tt[i+1][temp]+len[i]);
}
else
{
if(i==n) //区分是不是第n首歌，如果是，j<=len[i]时直接选择唱劲歌金曲，否则不唱当前的歌
{
d[i][j]=1;
tt[i][j]=678;
}
else
{
d[i][j]=d[i+1][j];
tt[i][j]=tt[i+1][j];
}
}
}
cout<<"Case "<<num<<": "<<d[1][t]<<" "<<tt[1][t]<<endl;
}
return 0;
}