机器分配题目链接

1013. 机器分配 - AcWing题库

机器分配题目类型

分组背包模板题+求具体方案模板题

机器分配代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 20;
const int M = 25;
int a[N][M];
int f[N][M];
int way[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;++j)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=m;++j)
        {
            f[i][j] = f[i-1][j];
            for(int k=0;k<=j;++k)
            {
                f[i][j]=max(f[i][j],f[i-1][j-k]+a[i][k]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    int x = m;
    for(int i=n;i;i--)
    {
        for(int k=0;k<=x;++k)
        {
            if(f[i][x]==f[i-1][x-k]+a[i][k])
            {
                way[i] = k;
                x = x-k;
                break;
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        cout << i << " " << way[i] <<endl;
    }
    return 0;
}

开心的金明题目链接

426. 开心的金明 - AcWing题库

开心的金明题目类型

01背包模板题

开心的金明代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 30010;

int f[N];
int main(){
    int n, m;
    cin>>n>>m;
    for(int i=0;i<m;++i)
    {
        int v, p;
        cin>>v>>p;
        for(int j=n;j>=v;--j)
        {
            f[j]=max(f[j],f[j-v]+v*p);
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

背包问题求具体方案题目链接

12. 背包问题求具体方案 - AcWing题库

背包问题求具体方案题目类型

求具体方案模板题

背包问题求具体方案代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int f[N][N];
int vi[N];
int w[N];
int main(){
    int n, v;
    cin>>n>>v;
    for(int i=1;i<=n;++i)
    {
        cin>>vi[i]>>w[i];
    }
    
    for(int i=n;i;--i)
    {
        for(int j=0;j<=v;++j)
        {
            f[i][j]=f[i+1][j];
            if(j>=vi[i])
            f[i][j]=max(f[i][j],f[i+1][j-vi[i]]+w[i]);
        }
    }
    
    int x = v;
    for(int i=1;i<=n;++i)
    {
        if(x>=vi[i]&&f[i+1][x]<=f[i+1][x-vi[i]]+w[i]){
            cout << i << " ";
            x -= vi[i];
        }
    }
    cout << endl;
    return 0;
}

金明的预算方案题目链接

487. 金明的预算方案 - AcWing题库

金明的预算方案题目类型

求具体方案模板题

金明的预算方案代码

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define v first
#define w second

typedef pair<int, int> PII;

const int N = 70, M = 32010;
int n, m;
PII master[N];
vector<PII> servent[N];
int f[M];

int main(){
    cin>>m>>n;
    for(int i=1;i<=n;++i)
    {
        int v, w, q;
        cin >> v >> w >> q;
        if(!q) master[i] = {v, v*w}; 
        else servent[q].push_back({v, v*w});
    }
    
    for(int i=1;i<=n;++i)
    {
        for(int j=m;j>=0;j--)
        {
            auto &sv = servent[i];
            for (int k=0;k< 1 << sv.size();k++)
            {
                int v = master[i].v;
                int w = master[i].w;

                for(int u=0;u<sv.size();u++)
                {
                    if(k>>u&1)
                    {
                        v+=sv[u].v;
                        w+=sv[u].w;
                    }
                }
                if(j>=v) f[j]=max(f[j],f[j-v]+w);
            }
        }
    }
    cout << f[m] <<endl;
    return 0;
}