学步园

HDU 2546 饭卡

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546

解析：将余额中的5元拿出来买最贵的物品，除去最贵的物品后在进行01背包。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

bool cmp(int a,int b)
{
	if(a>b)
		return true;
	return false;
}

int max(int a,int b)
{
	return a>b? a:b;
}

int main()
{
	int n,i,j,m,ans;
	int dp[2010];//一维余额，dp值是余额
	int v[2010];

	while(scanf("%d",&n)!=EOF,n)
	{
		memset(dp,0,sizeof dp);
		for(i=0;i<n;i++)
			scanf("%d",&v[i]);
		sort(v,v+n,cmp);

		scanf("%d",&m);
		if(m<5)
		{
			printf("%d\n",m);
			continue;
		}
		ans=5-v[0]; //拿出5块钱去买最贵的菜
		m-=5;
		//除去最贵的菜，剩下的01背包一遍
		for(i=1;i<n;i++)
		{
			for(j=m;j>=v[i];j--)
			{
				dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
			}
		}
		printf("%d\n",m-dp[m]+ans);
	}

return 0;
}
/*
3
8 3 6
10
-1

3
13 3 6
10
-6

3
10 13 3
6
-7

*/