那么我们把他们拆成两大部分来枚举, 一是 01, 二是完全.
而对于多重背包, 我们可以 n 个拆成 1+2+4..2^t-1<k(t 为满足关系的最大整数个数) 个 01 背包.
代码
- #include<bits/stdc++.h>
- #define maxn 1010000
- using namespace std;
- long long v[maxn],w[maxn],k[maxn];// 价值, 重量, 种类
- int n,T;
- int size;
- int t=1;
- long long dp[maxn];
- int main(){
- cin>>n>>T;
- int vv,ww,kk;// 价值, 重量
- for(int i=1;i<=n;i++){
- cin>>ww>>vv>>kk;
- if(kk==-1){//01 背包
- v[++size]=vv;
- w[size]=ww;
- k[size]=1;
- }
- else if(kk==0){// 完全背包
- v[++size]=vv;
- w[size]=ww;
- k[size]=0;
- }
- else if(kk>=1){// 多重背包拆解为 01 背包
- t=1;
- while(t<=kk){
- v[++size]=vv*t;
- w[size]=ww*t;
- k[size]=1;
- kk=kk-t;
- t <<= 1;
- }
- v[++size]=vv*kk;
- w[size]=ww*kk;
- k[size]=1;
- }
- }
- /*for(int i=1;i<=size;i++){
- cout<}*/
- dp[0]=0;
- for(int i=1;i<=size;i++){
- if(k[i]==1){
- for(int j=T;j>=w[i];j--){
- dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
- }
- }
- else if(k[i]==0){
- for(int j=w[i];j<=T;j++){
- dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
- }
- }
- }
- cout<<dp[T]<<endl;
- return 0;
- }
混合背包
来源: http://www.bubuko.com/infodetail-3265934.html