Posted on 2009-08-27 16:41
Uriel 閱讀(492)
評論(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;
}