常州Day7

背包

01背包

#include<bits/stdc++.h>
using namespace std;
int m,n,w[35],c[35];
int f[205];
int main(){
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i];
    }
    for(int i=1;i<=m;i++)f[i]=0;
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            if(w[i]<=j)f[j]=max(f[j],f[j-w[i]]+c[i]);
        }
    }
    cout<<f[m];
    return 0;
}

完全背包

#include<bits/stdc++.h>
using namespace std;
int m,n,w[35],c[35];
int f[205];
int main(){
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i];
    }
    for(int i=1;i<=m;i++)f[i]=0;
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(w[i]<=j)f[j]=max(f[j],f[j-w[i]]+c[i]);
        }
    }
    cout<<"max="<<f[m];
    return 0;
}

多重背包

#include<bits/stdc++.h>
using namespace std;
int n,m,v[505],w[505],s[505];
int f[6005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>s[i];
    }
    for(int i=0;i<=m;i++)f[i]=0;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++){
                f[j]=max(f[j],f[j-v[i]*k]+w[i]*k);
            }
        }
    }
    cout<<f[m];
    return 0;
}

混合背包

#include<bits/stdc++.h>
using namespace std;
int n,m,w[505],c[505],p[505];
int f[6005];
int main(){
    for(int i=0;i<=m;i++)f[i]=0;
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i]>>p[i];
        if(p[i]==0){
            for(int j=w[i];j<=m;j++){
                f[j]=max(f[j],f[j-w[i]]+c[i]);
            }
        }else {
            for(int j=m;j>=w[i];j--){
                for(int k=0;k<=p[i]&&k*w[i]<=j;k++){
                   f[j]=max(f[j],f[j-w[i]*k]+c[i]*k);
                }
            }
        }
    }
    cout<<f[m];
    return 0;
}

分组背包

#include<bits/stdc++.h>
using namespace std;
int v,n,t;
int w[35],c[35],p[35];
int z[15][35],num[15],T=0,dp[205];/*
z[i][j]表示第i组第j个物品的编号，num是每组物品个数，T是组数，
dp[i]表示容量为i时的最优答案*/
int main(){
    cin>>v>>n>>t;//容量，物品数量，组数
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i]>>p[i];
        if(p[i]>T)T=p[i];
        z[p[i]][++num[p[i]]]=i;//表示第 k 组的第 i 件物品的编号是多少
    }
    for (int k = 1; k <= T; k++)          // 循环每一组
        for (int i = v; i >= 0; i--)         // 循环背包容量
            for (int j = 1; j <= num[k]; j++)  // 循环该组的每一个物品
                if (i >= w[z[k][j]])             // 背包容量充足
                    dp[i] = max(dp[i],dp[i - w[z[k][j]]] + c[z[k][j]]);  // 像0-1背包一样状态转移
    cout<<dp[v];
    return 0;
}