首页 > 代码库 > [51nod]多重背包模板

[51nod]多重背包模板

2024-09-21 06:28:26   217人阅读

https://www.51nod.com/tutorial/course.html#!courseId=11

题目大意：

有$N$种物品和一个容量为$W$的背包。第$i$种物品最多有$c[i]$件可用，每件体积是$w[i]$，价值是$v[i]$。求解将哪些物品装

入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 

解题思路：采用二进制拆分的思想，将有限的背包划分为01背包和完全背包解决。

转移方程：$dp[i][j] = \max \{ dp[i - 1][v - k*w[i]] + k*v[i]|0 \le k \le c[i]\} $

 

 

 

 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int c[50002],w[50002],v[50002],N,W; 5 ll dp[50002]; 6 void bag01(int ww,int vv){ 7     for(int i=W;i>=ww;i--){ 8         dp[i]=max(dp[i],dp[i-ww]+vv); 9     }10 }11 void bagcomplete(int ww,int vv){12     for(int i=ww;i<=W;i++){13         dp[i]=max(dp[i],dp[i-ww]+vv);14     }15 }16 void bagmult(){17     memset(dp,0,sizeof dp);18     for(int i=0;i<N;i++){19         if(c[i]*w[i]>W){20             bagcomplete(w[i],v[i]);21         }22         else{23             int k=1;24             while(k<c[i]){25                 bag01(k*w[i],k*v[i]);26                 c[i]-=k;27                 k<<=1;28             }29             bag01(c[i]*w[i],c[i]*v[i]);30         }31     }32 }33 34 int main(){35     scanf("%d%d",&N,&W);36     for(int i=0;i<N;i++){37         scanf("%d%d%d",w+i,v+i,c+i);38     }39     bagmult();40     printf("%lld",dp[W]);41 }

 

[51nod]多重背包模板


联系
我们