Posted on 2009-08-27 16:41
Uriel 阅读(488)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
DP
这题丢了几天。。没想到是0-1背包。。。

/**//*Problem: 3628 User: Uriel
Memory: 9228K Time: 110MS
Language: C++ Result: Accepted*/

#include<stdio.h>
#include<stdlib.h>

int N,B,H[21],i,dp[21][20000002],j,sum,k;
int main()


{
scanf("%d %d",&N,&B);
sum=0;
for(i=1;i<=N;i++)

{
scanf("%d",&H[i]);
sum+=H[i];
}
for(j=N;j>=0;j--)

{
dp[j][0]=1;
}
for(i=1;i<=N;i++)

{
for(j=sum;j>=H[i];j--)

{
for(k=0;k<i;k++)

{
if(dp[k][j-H[i]]==1)

{
dp[i][j]=1;
}
}
}
}
for(i=B;i<=sum;i++)

{
for(j=1;j<=N;j++)

{
if(dp[j][i]==1)

{
printf("%d\n",i-B);
goto flag;
}
}
}
flag:system("PAUSE");
return 0;
}

