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

Problem  Description：

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

Input：

多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。

Output：

对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

Sample  Input：

1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0

Sample  Output：

-45
32

题目思路：将该问题转化成0-1背包问题，由于每个菜只能购买一次，而且每次买菜的时候饭卡余额 m 要大于等于5，因此先利用0-1背包算出 m - 5 的钱最多能买多少菜，然后拿最后的5块钱买最贵的菜，才能使饭卡余额达到最少。而且这道题还要注意的一点是在进行0-1背包之前要将所有的菜从小到大排一下序，因为要使饭卡余额最少必须要用最后5块钱买最贵的菜，而每个菜只能购买一次，因此要在0-1背包之前sort排序，防止最贵的菜购买了多次。

My  Code：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
int w[1005],f[1005],n,m;
void ZeroPack(int W)
{
    memset(f,0,sizeof(f));
    for(int i = 0; i < n-1; i++)///去掉最贵的菜之后进行0-1背包
    {
        for(int j = W; j >= w[i]; j--)
            f[j] = max(f[j],f[j-w[i]]+w[i]);
    }
}
int main()
{
    while(cin >> n)
    {
        if(n == 0) break;
        for(int i = 0; i < n; i++)
            cin >> w[i];
        sort(w,w+n);///对菜进行从小到大排序
        cin >> m;
        if(m < 5)///如果余额小于5，则输出饭卡值
            cout << m << endl;
        else
        {
            ZeroPack(m-5);
            m = m-f[m-5]-w[n-1];///先算出m-5最多能买多少菜，再用最后的5块钱买那个最贵的菜，得出的就是最小余额
            cout << m << endl;
        }
    }
}