DP

오래전에 이 문제를 풀었는데 밤에 잠이 안 와요. 니시스트가 DP를 넣는 경기를 보고 들어와서 간장을 쳤어요.
이 문제의 하이라이트는 최대치를 기록한 다음에 그 값을 0으로 바꾸는 것이다.그 다음은 그냥 가방이에요.
 

#include<stdio.h>

#include<string.h>

#define N 1005

int Max(int x,int y)

{

    if(x>y)

        return x;

    else

        return y;

}

int main()

{

    int n;

    int a[N],mark[N];

    while(scanf("%d",&n),n)

    {

        int max,flag;

        int i,j;

        flag=-1;

        max=0;

        int sum=0;

        for(i=0;i<n;i++)

        {

            scanf("%d",&a[i]);

            sum+=a[i];

            if(a[i]>max)

            {

                max=a[i];

                flag=i;

            }

        }

        int v;

        scanf("%d",&v);

        if(v<5)

        {

            printf("%d
",v);

            continue;

        }

        if(v-sum>=5)

        {

            printf("%d
",v-sum);

            continue;

        }

        a[flag]=0;

        v-=5;

        memset(mark,0,sizeof(mark));

        for(i=0;i<n;i++)

        {

            for(j=v;j>=a[i];j--)

                mark[j]=Max(mark[j],mark[j-a[i]]+a[i]);

        }

        v=v+5-mark[v]-max;

        printf("%d
",v);

    }

    return 0;

}