算法基础课背包问题代码

2.01背包问题

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N],w[N],v[N],n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);
    printf("%d",f[m]);
    return 0;
}

3.完全背包问题

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N],w[N],v[N],n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)f[j]=max(f[j],f[j-v[i]]+w[i]);
    printf("%d",f[m]);
    return 0;
}

4.多重背包问题I 暴力解法

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N],w[N],v[N],s[N],m,n;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&v[i],&w[i],&s[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    printf("%d",f[n][m]);
    return 0;
}

5.多重背包问题II 二进制优化

#include<bits/stdc++.h>
using namespace std;
const int N = 25010;
int f[N],v[N],w[N],n,m;
int main(){
    scanf("%d%d",&n,&m);
    int cnt = 0;
    for(int i=1;i<=n;i++){
        int a,b,s;scanf("%d%d%d",&a,&b,&s);
        int k=1;
        while(k<=s){
            cnt++;
            v[cnt] = a*k;
            w[cnt] = b*k;
            s-=k;
            k*=2;
        }
        if(s>0){
            cnt++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    n = cnt;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)f[j] = max(f[j],f[j-v[i]]+w[i]);
    printf("%d",f[m]);
    return 0;
}

9.分组背包问题

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N],v[N][N],w[N][N],s[N],n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        for(int j=0;j<s[i];j++)scanf("%d%d",&v[i][j],&w[i][j]);
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=0;k<s[i];k++)
                if(v[i][k]<=j){
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
                }
    printf("%d",f[m]);
    return 0;
}