很久以前做过这道题，晚上睡不着，看见nyist加了一个DP的比赛，就进来打个酱油。

这道题的点睛之笔是将最大值记录下来，然后将其值改为0。之后就是普通的背包了。

 

#include
    
     #include
     
      #define N 1005int 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
      
       max)            {                max=a[i];                flag=i;            }        }        int v;        scanf("%d",&v);        if(v<5)        {            printf("%d\n",v);            continue;        }        if(v-sum>=5)        {            printf("%d\n",v-sum);            continue;        }        a[flag]=0;        v-=5;        memset(mark,0,sizeof(mark));        for(i=0;i
       
        =a[i];j--)                mark[j]=Max(mark[j],mark[j-a[i]]+a[i]);        }        v=v+5-mark[v]-max;        printf("%d\n",v);    }    return 0;}