HDU 3535 AreYouBusy

题目链接~~>

做题感悟： 背包问题分着还好解决，如果和起来就是一个很吓人的题。

解题思路： 有三种状态 1 )  每组至少选择一个  2 ) 每组最多选择一个（分组背包）  3 )  每组可以选多个（01背包）

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define lld __int64
     
    
   

    

     

    
    

     

      const double PI = 3.1415926 ;
     
    
   

    

     

    
    

     

      const double esp = 1e-4 ;
     
    
   

    

     

    
    

     

      const int  md= 2810778 ;
     
    
   

    

     

    
    

     

      const int INF = 999999999 ;
     
    
   

    

     

    
    

     

      const int MX = 105 ;
     
    
   

    

     

    
    

     

      int n,m ;
     
    
   

    

     

    
    

     

      int dp[MX][MX] ;
     
    
   

    

     

    
    

     

      void searchA(int nx,int k) // 至少选择一个
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
   int v,w ;
     
    
   

    

     

    
    

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

    

     

    
    

     

         {
     
    
   

    

     

    
    

     
 scanf("%d%d",&v,&w) ;
     
    
   

    

     

    
    

     
 for(int j=m ;j>=v ;j--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(dp[k][j-v]!=-1) // 两个 if 位置不能换
     
    
   

    

     

    
    

     

       dp[k][j]=max(dp[k][j],dp[k][j-v]+w) ;
     
    
   

    

     

    
    

     
 if(dp[k-1][j-v]!=-1)
     
    
   

    

     

    
    

     

       dp[k][j]=max(dp[k][j],dp[k-1][j-v]+w) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

         }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void searchB(int nx,int k) // 最多选择一个 相当于分组背包
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int v,w ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       dp[k][i]=dp[k-1][i] ;
     
    
   

    

     

    
    

     
 for(int j=0 ;j<nx ;j++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&v,&w) ;
     
    
   

    

     

    
    

     
 for(int i=m ;i>=v ;i--) // 每次都是从上一个状态转移到当前组的状态
     
    
   

    

     

    
    

     
 if(dp[k-1][i-v]!=-1)
     
    
   

    

     

    
    

     

       dp[k][i]=max(dp[k][i],dp[k-1][i-v]+w) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void searchC(int nx,int k) // 随便选 相当于 01 背包
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int v,w ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<=m ;i++) // 必须放在这里，如果放在里面最优值会被替换
     
    
   

    

     

    
    

     

       dp[k][i]=dp[k-1][i] ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&v,&w) ;
     
    
   

    

     

    
    

     
 for(int j=m ;j>=v ;j--)
     
    
   

    

     

    
    

     
 if(dp[k][j-v]!=-1)
     
    
   

    

     

    
    

     

       dp[k][j]=max(dp[k][j],dp[k][j-v]+w) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void init() // 初始化
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       dp[i][j]=-1 ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       dp[0][i]=0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int nx,cs ;
     
    
   

    

     

    
    

     
 while(~scanf("%d%d",&n,&m))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&nx,&cs) ;
     
    
   

    

     

    
    

     
 if(!cs) // 至少选一个
     
    
   

    

     

    
    

     

       searchA(nx,i) ;
     
    
   

    

     

    
    

     
 else if(cs==1) // 最多选一个
     
    
   

    

     

    
    

     

       searchB(nx,i) ;
     
    
   

    

     

    
    

     
 else if(cs==2) // 随便选
     
    
   

    

     

    
    

     

       searchC(nx,i) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

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

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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