Uva 12563，劲歌金曲，01背包

题目链接：https://uva.onlinejudge.org/external/125/12563.pdf

题意：n首歌，每首歌的长度给出，还剩 t 秒钟，由于KTV不会在一首歌没有唱完的情况下切歌，求在总曲目尽量多的情况下，唱的最久。

分析：

刚开始，题意看错了，结果就按01背包模板了，求了在 t 时间下唱的最久，然后再找出唱了几首歌。WA到疯了，最后实在是崩溃啊！

然后，这个题目没做出来，主要还是01背包没弄透彻。可以利用二维 [2][t] 的滚动数组求路径，这里不仅是优化了空间，而且，当我找到最优值的时候，可以很快找到路径 [p^1][]之前已经被覆盖，也就是说，哪些歌被选了，就有[p^1][t] == ans;

然后要理解p^1,这样的覆盖，刚开始p=1;p^1,进行了初始化，递推，每递推一层，p = p^1;最后，p被转化到下一个状态了，在找路径的时候要转化回来。

/*
#include <bits/stdc++.h>
using namespace std;

#define C 1000000

int v[55];
int w[55];
int f[C];

int main()
{

    int T;
    int cases = 1;
    scanf("%d",&T);
    while(T--)
    {
        int n,t;
        scanf("%d%d",&n,&t);

        int temp;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&temp);
            v[i] = temp;
            w[i] = temp;
        }

        memset(f,0,sizeof(f));

        for(int i=1; i<=n; i++)
        {
            for(int j=t; j>=0; j--)
            {
                if(j>=v[i])
                    f[j] = max(f[j],f[j-v[i]]+w[i]);
            }
        }

        //printf("%d
",f[t]);
        //printf("%d
",f[t-1]);

        vector<int> ans;
        ans.clear();
        int sum = f[t];
        for(int i=n; i>=1; i--)
        {
            if(sum-v[i]==f[sum-v[i]])
            {
                ans.push_back(v[i]);
                sum-=v[i];
            }
        }

        sort(ans.begin(),ans.end());

        if(f[t]>=t)
        {
            ans.clear();
            int the_ans=-1;
            for(int i=0; i<t; i++)
            {
                if(f[i]<f[t])
                {
                    if(f[i]>the_ans)
                        the_ans = f[i];
                }
            }
            int sum = the_ans;
            for(int i=n; i>=1; i--)
            {
                if(sum-v[i]==f[sum-v[i]])
                {
                    ans.push_back(v[i]);
                    sum-=v[i];
                }
            }
            printf("Case %d: %d %d
",cases++,ans.size()+1,the_ans+678);
        }
        else if(f[t]<t)
            printf("Case %d: %d %d
",cases++,ans.size()+1,f[t]+678);

    }

    return 0;
}
*/

#include <bits/stdc++.h>
using namespace std;

int n,t;

const int maxn=55;

int len[maxn];
int d[2][maxn*180+678];

int main()
{
    int T;
    scanf("%d",&T);

    for(int kase = 1; kase<=T; kase++)
    {
        scanf("%d%d",&n,&t);
        for(int i=1; i<=n; i++)
            scanf("%d",&len[i]);

        for(int i=0; i<t; i++)
            d[0][i] = -1;
        d[0][0] = 0;

        int p = 1,ans =0;
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<t; j++)
            {
                d[p][j] = d[p^1][j];
                if(j>=len[i]&&d[p^1][j-len[i]]>=0)
                {
                    d[p][j] = max(d[p][j],d[p^1][j-len[i]]+1);
                }
                ans = max(ans,d[p][j]);
            }
            p = p^1;
        }
        for(int i=t-1; i>=0; i--)
        {
            if(d[p^1][i]==ans)
            {
                printf("Case %d: %d %d
",kase,ans+1,i+678);
                break;
            }
        }
    }

    return 0;
}