HDU 2546饭卡

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;

int dp[1200][1200];
int a[1200];
int main()
{
    int n;//n个菜 
    int yue;
    int sum;
    int f1,f2;
    while(cin>>n&&n!=0)
    {
        sum=0;
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        cin>>yue;
        if(yue<5) cout<<yue<<endl;
        else
        {
            sort(a+1,a+n+1);
            sum=yue-5;
            for(int i=1;i<=n-1;i++)
            {
                for(int j=0;j<=sum;j++)
                {
                    if(j>=a[i])
                    {
                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]]+a[i]);
                    }
                    else  dp[i][j] = dp[i-1][j];
                }   
            }
            yue=yue-dp[n-1][sum]-a[n];
            cout<<yue<<endl;
        }
    }
    return 0;
}