HDU2546饭卡（01背包）

解题思路：纯01背包，注意一点它问最少能达到多少钱，我们可以把所有的取好（费用大于等于5元），最后一次再买价值最大的菜，这样一定最少。关键就是怎么使费用大于等于5元呢？你可以限定背包的最大容量-5，这样就一定能至少预留5的容量给价值最大的东西。dp[i]表示手里i元的时候能拿到多少元的菜。注意他给你的钱不一定>=5!QAQ

AC代码如下：

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

int dp[1010],v[1010],n,m;

int main()
{
	int i,j,temp;
	while(cin>>n && n)
	{
		for(i=1;i<=n;i++)
			cin>>v[i];
		sort(v+1,v+n+1);
		cin>>m;
		memset(dp,0,sizeof(dp));
		if(m>=5)
		{
			for(i=1;i<n;i++)
				for(j=m-5;j>=v[i];j--)
				{
					if(dp[j]<dp[j-v[i]]+v[i])
					{
						dp[j]=dp[j-v[i]]+v[i];
					}
				}
			cout<<m-dp[m-5]-v[n]<<endl;
		}
		else
			cout<<m<<endl;
	}
	return 0;
}