UVA12563Jin Ge Jin Qu hao(01背包)

紫书P274

题意：输入N首歌曲和最后剩余的时间t，问在保证能唱的歌曲数目最多的情况下，时间最长；最后必唱《劲歌金曲》

所以就在最后一秒唱劲歌金曲就ok了，背包容量是t-1，来装前面的歌曲，设两个Time求时间，cnt是数量

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;

const int MAX = 10000;

int cnt[MAX],Time[MAX],song[MAX];

int main()

{

    int n,t;

    int tase,num = 0;

    scanf("%d", &tase);

    while( tase-- )

    {

        scanf("%d%d", &n, &t);

        for(int i = 1; i <= n; i++)

            scanf("%d", &song[i]);

        int v = t - 1;

        memset(cnt, 0, sizeof(cnt));

        memset(Time, 0, sizeof(Time));

        for(int i = 1; i <= n; i++)

        {

            for(int j = v; j >= song[i]; j--)

            {

                if(cnt[j] < cnt[j - song[i]] + 1)   //选择第i个时的数量多

                {

                    cnt[j] = cnt[j - song[i]] + 1;

                    Time[j] = Time[j - song[i]] + song[i];

                }

                else if(cnt[j] == cnt[j - song[i]] + 1) //在数量相等的情况下，更新时间

                {

                    if(Time[j] < Time[j - song[i]] + song[i])

                        Time[j] = Time[j - song[i]] + song[i];

                }

            }

        }

        int res =678 + Time[v];

        printf("Case %d: %d %d\n",++num, cnt[v] + 1, res);

    }

    return 0;

}