Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3628 Bookshelf 2---0-1背包

Posted on 2009-08-27 16:41 Uriel 阅读(485) 评论(0)  编辑 收藏 引用 所属分类: POJDP

这题丢了几天。。没想到是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;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理