机器分配

题目 机器分配

思路分析

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=20;
int f[N][N];//从前i"组"物品中选 总体积不超过j的所有方案 属性max
int w[N][N];
int n,m;
int path[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    //实际含义出发 第1个物品 选1件 所以从1开始读 另外 选0件价值就是0 不需要初始化
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>w[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<=m;k++){//选的话 再枚举组内选法 共m种
                if(k<=j){//当然得放得下才能选 这两步可以合并 k<=m直接变成k<=j
                    f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k]);
                }
            }
        }
    }
    cout<<f[n][m]<<endl;

    for(int i=n,j=m;i;i--){//没要求字典序 所以可以正着dp 倒着推
        for(int k=0;k<=m;k++){
            if(k<=j && f[i][j]==f[i-1][j-k]+w[i][k]){//贪心思想在 能选就一定选
                path[i]=k;
                j-=k;
                break;
            }
        }
    }

    for(int i=1;i<=n;i++)   cout<<i<<" "<<path[i]<<endl;

    return 0;
}

同类题型

视频讲解

⬅️ 背包问题的转换 🏠 00-冲刺国赛 ➡️ 金明的预算方案