学步园

Uva Jin Ge Jin Qu

题实质：n个物品选k个 求总价值小于t的最大总价值

使用背包，队长点拨，忽然领悟，背包火候不够啊。。。。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=10007;
const int JGJQ=678;
int x[MAXN];
int sum[MAXN];
int dp[MAXN];
int ans,nans;

int main()
{
	int T,id=0;
	scanf("%d",&T);
	while(T--)
	{
		int n,t;
		scanf("%d%d",&n,&t);
		int i,j;
		for(i=1;i<=n;i++)
		{
			scanf("%d",x+i);
		}

		sort(x+1,x+n+1);
		ans=nans=sum[0] = 0;
		for(i=1;i<=n;i++)
		{
			sum[i] = sum[i-1] + x[i];
			if(sum[i] < t)
			{
				nans = i;
				ans = sum[i];
			}
		}
		if(nans != n)
		{
			memset(dp,-1,sizeof(dp));
			dp[0] = 0;
			for(i=1;i<=n;i++)
			{
				for(j = t-1; j >= x[i]; j--)
				{
					if(dp[ j - x[i] ] >= 0)
					{
						dp[j] = max(dp[j] , dp[j-x[i]] + 1);
					}
				}
			}
			for(i=t-1;i>=0;i--)
			{
				if(dp[i] == nans)
				{
					ans = max(ans,i);
					break;
				}
			}
		}
		printf("Case %d: %d %d\n",++id,nans+1,ans+JGJQ);
	}
	return 0;
}