重庆制作网站培训/太原seo排名优化公司

对我而言是个比较难想到的01背包问题，不过实质就是在标准的01背包问题框架下将比较展开层次，在满足曲目最多的条件下再满足唱的时间尽量多。所以dp数组是个结构体数组。代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int a[100];
struct node
{
    int n,t;
} dp[52][10000];
int main()
{
    int T;
    scanf("%d",&T);
    int cas=0;
    while(T--)
    {
        int n,t;
        scanf("%d%d",&n,&t);
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
            for(int i=0;i<=n;i++)
                for(int j=0;j<=t;j++)
            {
                dp[i][j].n=0;
                dp[i][j].t=0;
            }
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<t; j++)
            {
                if(j<a[i])
                {
                    dp[i][j].n=dp[i-1][j].n;
                    dp[i][j].t=dp[i-1][j].t;
                }
                else
                {
                    if(dp[i-1][j].n<dp[i-1][j-a[i]].n+1)
                    {
                        dp[i][j].n=dp[i-1][j-a[i]].n+1;
                                   dp[i][j].t=dp[i-1][j-a[i]].t+a[i];
                    }
                    else if(dp[i-1][j].n==dp[i-1][j-a[i]].n+1)
                    {
                        if(dp[i-1][j].t<=dp[i-1][j-a[i]].t+a[i])
                        {
                            dp[i][j].n=dp[i-1][j-a[i]].n+1;
                                       dp[i][j].t=dp[i-1][j-a[i]].t+a[i];
                        }
                        else
                        {
                            dp[i][j].n=dp[i-1][j].n;
                            dp[i][j].t=dp[i-1][j].t;
                        }
                    }
                    else
                    {
                        dp[i][j].n=dp[i-1][j].n;
                            dp[i][j].t=dp[i-1][j].t;
                    }
                }
            }


        }
        cout<<"Case "<<++cas<<": "<<dp[n][t-1].n+1<<" "<<dp[n][t-1].t+678<<endl;
    }
}