很久以前做過這道題,晚上睡不著,看見nyist加了一個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\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<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\n",v); } return 0; }