hdu 2546 饭卡

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;

int main()
{
    int n,w[1024],i,j,d[1024],m,maxx,f;
    while(~scanf("%d",&n)&&n)
    {
        maxx=0;
        for(i=0; i<n; i++)
        {
            scanf("%d",&w[i]);
            if(w[i]>maxx) {maxx=w[i];f=i;}
        }
        scanf("%d",&m);
        memset(d,0,sizeof(d));
        if(m<5) printf("%d
",m);
        else {
        for(i=0;i<n;i++)
        {
            if(i!=f)
            for(j=m-5;j>=w[i];j--)
                d[j]=max(d[j],d[j-w[i]]+w[i]);
        }
        printf("%d
",m-d[m-5]-maxx);
        }
    }
    return 0;
}

二维

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;

int d[1024][1024];
int main()
{
    int n,w[1024],i,j,m,maxx,f;
    while(~scanf("%d",&n)&&n)
    {
        maxx=0;
        w[0]=0;
        for(i=1; i<=n; i++)
        {
            scanf("%d",&w[i]);
            if(w[i]>maxx)
            {
                maxx=w[i];
                f=i;
            }
        }
        scanf("%d",&m);
        memset(d,0,sizeof(d));
        if(m<5) printf("%d
",m);
        else
        {
            for(i=1; i<=n; i++)
            {
                if(i!=f)
                {
                    for(j=0; j<=m-5; j++)
                    {
                        if(j>=w[i])
                            d[i][j]=max(d[i-1][j],d[i-1][j-w[i]]+w[i]);
                        else d[i][j]=d[i-1][j];
                    }
                }
                else
                {
                    for(j=0; j<=m-5; j++)
                   d[i][j]=d[i-1][j];
                }
            }
            printf("%d
",m-d[n][m-5]-maxx);
        }
    }
    return 0;
}