NYOJ 860 又见01背包

题目链接~~>

做题感悟：这题是在做周赛时接触的，一看题目感觉很简单，又一看数据没法开数组，那就只有用搜索了，果断超时。

解题思路：因为价值最多才 1e4 所以可以把价值看成背包的容量，选的时候选重量轻的，之后再从最大价值开始遍历，只要重量满足就 break ;

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      const int INF =1e9+5 ;
     
    
   

    

     

    
    

     

      int w[105],v[105],dp[10005] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j,n,m ;
     
    
   

    

     

    
    

     
 while(scanf("%d%d",&n,&m)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int sum=0 ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&w[i],&v[i]) ;
     
    
   

    

     

    
    

     

       sum+=v[i] ; // 价值上限
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       dp[0]=0 ;
     
    
   

    

     

    
    

     
 for(i=1 ;i<=sum ;i++)
     
    
   

    

     

    
    

     

       dp[i]=INF ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(dp[j]>dp[j-v[i]]+w[i])
     
    
   

    

     

    
    

     

       dp[j]=dp[j-v[i]]+w[i] ;
     
    
   

    

     

    
    

     
 for(j=sum ;j>=0 ;j--)
     
    
   

    

     

    
    

     
 if(dp[j]<=m)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("%d\n",j) ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/18084857