hdu 2546 0-1背包

#include<stdio.h>
#include<string.h>
#define N 1100
int dp[N],a[N];
int main() {
int n,m,i,j,max,k;
while(scanf("%d",&n),n) {
max=0;k=0;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>max) {
max=a[i];
k=i;
}
}
scanf("%d",&m);
if(m<5) {//如果不够5元就直接输出
printf("%d ",m);
continue;
}
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++) {
if(i==k)
continue;
for(j=m-5;j>=a[i];j--)//以m-5为最大容量
if(dp[j]<dp[j-a[i]]+a[i])
dp[j]=dp[j-a[i]]+a[i];
}
k=0;
for(i=1;i<=m;i++)//找出最大值
if(k<dp[i])
k=dp[i];
printf("%d ",m-k-max);
}
return 0;
}