C++背包问题,包涵01,多重

01背包:

#include <iostream>
#include <cstdio>
using namespace std;
int a[105][2];int b[105][11];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i][0];
    }
    for(int i=1;i<=n;i++){
        cin>>a[i][1];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=10;j++){
            if(j>=a[i][0]){
                b[i][j]=max(b[i-1][j],a[i][1]+b[i-1][j-a[i][0]]);
            } 
            else{
                b[i][j]=b[i-1][j];
            }
        }
    }
    cout<<b[n][10];
    return 0;
}

01(1维存储):

#include <iostream>
#include <cstdio>
using namespace std;
int a[105],b[105],c[11];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=10;j>=0;j--){
            if(j>=a[i]){
                c[j]=max(c[j],b[i]+c[j-a[i]]);
            } 
        }
    }
    cout<<c[10];
    return 0;
}

多重背包

#include <iostream>
#include <cstdio>
using namespace std;
int v[105],c[105],n[105],lst[105][11];
int main(){
    int s;
    cin>>s;
    for(int i=1;i<=s;i++){
        cin>>c[i];
    }
    for(int i=1;i<=s;i++){
        cin>>v[i];
    }
    for(int i=1;i<=s;i++){
        cin>>n[i];
    }
    for(int i=1;i<=s;i++){
        for(int j=0;j<=10;j++){
            for(int k=0;k<=n[i];k++){
                if(j>=c[i]*k){
                    lst[i][j]=max(lst[i][j],v[i]*k+lst[i-1][j-c[i]*k]);

                }
            }
            //cout<<lst[i][j]<<" ";
        }
        //cout<<endl;
    }
    cout<<lst[s][10];
    return 0;
}

原文链接: https://www.cnblogs.com/theflight/p/bag.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367410

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

C++背包问题,包涵01,多重

相关推荐