UVA 624 - CD (01背包打印路径)

题目链接~~>

做题感悟：本来以为就一种结果搞了好久没搞定，然后用前天看的01背包打印路径的方法，但是必须用二维的数组果断超时，因为没看到第一维只有20！！。

解题思路：这题属于价值和重量相等的01背包问题，只是题目还要求输出路径（只要输出一种即可）。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int dp[10005],w[10005] ;
     
    
   

    

     

    
    

     

      bool path[25][10005] ; // 路径记录
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j,n,m ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     
 memset(path,false,sizeof(path)) ;
     
    
   

    

     

    
    

     
 memset(dp,0,sizeof(dp)) ;
     
    
   

    

     

    
    

     
 for(i=n-1 ;i>=0 ;i--) // i从n到0便于打印路径
     
    
   

    

     

    
    

     
 for(j=m ;j>=w[i] ;j--)
     
    
   

    

     

    
    

     
 if(dp[j]<dp[j-w[i]]+w[i])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       path[i][j]=true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       j=m ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)  // 打印路径
     
    
   

    

     

    
    

     
 if(path[i][j])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("%d ",w[i]) ;
     
    
   

    

     

    
    

     

       j-=w[i] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("sum:%d\n",dp[m]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int dp[25][10005],w[10005] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int n,m,i,j ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     
 memset(dp,0,sizeof(dp)) ; // 一定要有
     
    
   

    

     

    
    

     
 for(i=n ;i>=1 ;i--)
     
    
   

    

     

    
    

     
 for(j=0 ;j<=m ;j++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dp[i][j]=(i==n ? 0 : dp[i+1][j]) ;
     
    
   

    

     

    
    

     
 if(j>=w[i]&&dp[i][j]<dp[i+1][j-w[i]]+w[i])
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       j=m ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(dp[i][j]>dp[i+1][j])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("%d ",w[i]) ;
     
    
   

    

     

    
    

     

       j-=w[i] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("sum:%d\n",dp[1][m]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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