ZOJ 3703 Happy Programming Contest

题目链接~~>

做题感悟：这题比赛时想了好久才做出来，赛后一想其实就是 01 背包一下，记录各个体积的最优值就可以了，比赛时想多了。

解题思路：

               我直接开的二维数组 dp[ i ] [ j ]  代表达到体积 i ,做了 j 道题所达到的最优状态 ： dp[ i ] [ j ]  = { dp [ i - v ] [ j - 1 ] } 的最优值 ，其实就是二维的背包 。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      const int INF = 0x3f3f3f3f ;
     
    
   

    

     

    
    

     

      const int MX = 1000 + 10 ;
     
    
   

    

     

    
    

     

      int C ,n ;
     
    
   

    

     

    
    

     

      int dp[2][MX][55] ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int v ,w ;
     
    
   

    

     

    
    

     

      }T[MX] ;
     
    
   

    

     

    
    

     

      bool cmp(node a, node b)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(a.v == b.v)  return a.w > b.w ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     
 return a.v < b.v ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void input()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 scanf("%d%d" ,&C ,&n) ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 //freopen("input.txt" ,"r" ,stdin) ;
     
    
   

    

     

    
    

     
 int Tx ;
     
    
   

    

     

    
    

     
 scanf("%d" ,&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       input() ;
     
    
   

    

     

    
    

     
 int ans = 0 ,num = 0 ,Wx = INF ;
     
    
   

    

     

    
    

     

       sort(T ,T+n ,cmp) ;
     
    
   

    

     

    
    

     
 memset(dp[0] ,-1  ,sizeof(dp[0])) ;
     
    
   

    

     

    
    

     
 memset(dp[1] ,0 ,sizeof(dp[1])) ;
     
    
   

    

     

    
    

     

       dp[0][0][0] = 0 ;
     
    
   

    

     

    
    

     
 for(int t = 1 ;t <= n ; ++t)
     
    
   

    

     

    
    

     
 for(int j = C  ;j >= T[t-1].v ; --j)
     
    
   

    

     

    
    

     
 for(int i = t ;i >= 1 ; --i)
     
    
   

    

     

    
    

     
 if(dp[0][j-T[t-1].v][i-1] != -1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int v = T[t-1].v ;
     
    
   

    

     

    
    

     
 int w = T[t-1].w ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

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

    

     

    
    

     

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

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(dp[0][j][i] == dp[0][j-v][i-1] + w && dp[1][j][i] > dp[1][j-v][i-1] + j)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

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

    

     

    
    

     

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

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(dp[0][j][i] > ans || (dp[0][j][i] == ans && i > num) || (dp[0][j][i] == ans && i == num && Wx > dp[1][j][i]))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ans = dp[0][j][i] ;
     
    
   

    

     

    
    

     

       num = i ;
     
    
   

    

     

    
    

     

       Wx = dp[1][j][i] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(Wx != INF)
     
    
   

    

     

    
    

     
 cout<<ans<<" "<<num<<" "<<Wx<<endl ;
     
    
   

    

     

    
    

     
 else cout<<"0 0 0"<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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