HDU 2191 【多重背包】-白红宇

HDU 2191 【多重背包】

阅读量：5038 次

发布时间：2019-06-12

本文共 3560 字，大约阅读时间需要 11 分钟。

Input

输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

Output

对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

Sample Input

8 2

2 100 4

4 100 2

Sample Output

400

【分析】：

【代码】：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,n,x) for(int i=(x); i<(n); i++)#define in freopen("in.in","r",stdin)#define out freopen("out.out","w",stdout)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int MAXN = 1e3 + 5;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int n,m,k;int num[maxm];int v[maxm], w[maxm],dp[maxm];int main(){ int t; cin>>t; while(t--) { ms(dp,0); cin>>m>>n; for(int i=0;i
                       
                        >w[i]>>v[i]>>num[i]; } for(int i=0;i
                        
                         =w[i]; j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } } cout<
                         
                          <

【二进制优化】：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,n,x) for(int i=(x); i<(n); i++)#define in freopen("in.in","r",stdin)#define out freopen("out.out","w",stdout)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int MAXN = 1e3 + 5;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int n,m,k;int num[maxm];int v[maxm], w[maxm],dp[maxm];void zero(int cost ,int value){ for(int j=m;j>=cost;j--){ dp[j]=max(dp[j],dp[j-cost]+value); }}void cmp(int cost, int value){ for(int j=cost;j<=m;j++){ dp[j]=max(dp[j],dp[j-cost]+value); }}void mul(int cost, int value,int cnt){ if(m<=cnt*cost) { cmp(cost,value); return ; } else{ int k=1; while(k<=cnt){ zero(k*cost,k*value); cnt-=k; k<<=1; } } zero(cnt*cost,cnt*value);}int main(){ int t; cin>>t; while(t--) { ms(dp,0); cin>>m>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>v[i]>>num[i]; } for(int i=1;i<=n;i++){ mul(w[i],v[i],num[i]); } cout<
                       
                        <

转载于:https://www.cnblogs.com/Roni-i/p/9055792.html

你可能感兴趣的文章