分析：这是一个01背包的变种，加入了贪心的思想。
这里我们思考
(1)如果m<5那么无法进行购买，剩余值为m
(2)如果m>=5 这个时候我们利用5元就可以购买到最有价值的菜，然后
使用m-5购买剩余的。那么m-5是背包的容量，剩余的菜是所选物品。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int n,m,v[1002],dp[50000],sum,V;
while (scanf("%d",&n)!=EOF)
{
if(n==0) break;
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
sum+=v[i];
}
scanf("%d",&m);
//对价格进行排序
//只针对前n-1进行背包，求出可取的最大值
sort(v+1,v+1+n);
memset(dp,0,sizeof(dp));
V=m-5; //利用5元购买价值最贵的菜，其他进行背包
for(int i=1;i<n;i++)
for(int j=V;j>=v[i];j--)
dp[j]=dp[j]>dp[j-v[i]]+v[i]?dp[j]:dp[j-v[i]]+v[i];
//如果m<5则不能购买任何菜
//dp[V]+v[n]表示能买的最多菜，m-dp[V]-v[n]剩余钱
printf("%d
",m<5?m:m-dp[V]-v[n]);
}
return 0;
}