多重背包&二进制优化&单调队列优化

参考：多重背包问题大全(超详细)_曼切斯特的流氓的博客-CSDN博客_多重背包问题 

三重循环复杂度；

【注意：这是把多重背包拆分成 01背包 所以在用一维dp数组的时候，体积记得要倒着来！！！】

【注意这里是外层枚举体积，内层枚举物品个数】

4. 多重背包问题 I - AcWing题库

#include
using namespace std;
int dp[120];
int s,v,w;
int main()
{
    int m,n;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>s;
        for(int j=m;j>0;j--){
            for(int k=1;k<=s&&j-v*k>=0;k++){
                dp[j]=max(dp[j],dp[j-v*k]+w*k);
            }
        }
    }
    cout< 
二进制优化多重背包 
通过二进制来代表拿的物品数，用二进制将同种物品 分别 合并；
 
【注意：外层枚举新合成出来的物品，内层枚举体积】
 
5. 多重背包问题 II - AcWing题库
 
#include 
using namespace std;
int n,m,v[15],w[15],dp[2010];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int cnt=0;int tiji,jia,s;
        cin>>tiji>>jia>>s;
        for(int k=1; k<=s; k<<=1){
            v[++cnt]=k*tiji;w[cnt]=k*jia;
            s-=k;
        }
        if(s){v[++cnt]=s*tiji;w[cnt]=s*jia;}
        for(int k=1;k<=cnt;k++){
            for(int j=m;j>=0&&j-v[k]>=0;j--){
               dp[j]=max(dp[j],dp[j-v[k]]+w[k]);
            }
         } 
    }
    cout< 
单调队列优化  
 
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714766.html