01背包+贪心

贪心：先买价格低的，价格高的尽量留到最后买(余额尽量接近5)

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

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

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

# include<bits/stdc++.h>
using namespace std;

const int N = 1006;
int f[N][N];
int n,m;
int a[N];

bool cmp(int x, int y)
{
    return x>y;
}

void init()
{
    memset(f, 0x3f, sizeof f);
    for(int i = 0; i<=m; i++) f[0][i] = i; 
    for(int i = 1; i<=n; i++)
        for(int j = 0; j<=4; j++)
            f[i][j] = j;

}

int main()
{
    while(cin>>n && n!=0)
    {
        for(int i = 1; i<=n; i++)
            scanf("%d",a+i);
        sort(a+1,a+1+n,cmp);
        cin>>m;

        init();

        for(int i = 1; i<=n; i++)
        {
            for(int j = 5; j<=m; j++)
            {
                f[i][j] = f[i-1][j];
                if(j>=a[i]) f[i][j] = min(f[i][j],f[i-1][j-a[i]]);
                else f[i][j] = min(f[i][j],j-a[i]);
            }
        }
        for(int i = 0; i<=n; i++)
        {
            for(int j = 1; j<=m; j++)
                cout<<f[i][j]<<" ";
            cout<<endl;
        }
        cout<<f[n][m]<<endl;
    }
}