HDU2546 （01背包）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e3+5;
const int inf=0x3f3f3f3f;
int read()
{
    int x=0,t=1;
    char ch=getchar();
    while(!isdigit(ch)){ if(ch=='-')t=-1; ch=getchar(); }
    while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); }
    return x*t;
}
int w[N],f[N<<1];
int main()
{
    int n,m;
    while(scanf("%d",&n)==1&&n)
    {
        memset(f,0,sizeof(f) );
        for(int i=1;i<=n;i++)
            w[i]=read();
        m=read();
        sort(w+1,w+n+1);
        for(int i=1;i<n;i++)
            for(int j=m;j>=w[i];j--)
                f[j]=max(f[j-w[i]]+w[i],f[j]);
        printf("%d
",m>=5?m-f[m-5]-w[n]:m );
        ///贪心，为使最后值最小，最后一次必须取最大。
        ///求出f[m-5] 最多能花多少钱 ，f[m-5]<=m-5<=m;
        ///如果求f[m-4] 那么就不能再减max,
        ///因为m-4>f[m-4]则f[m-4]<=m-5,所以可以直接算f[m-5],否则f[m-4]=m-4,就肯定不能再用钱了。
    }
    return 0;
}