---
title: "机器分配"
created: 2025-11-28
tags:
  - 算法
---

# 机器分配

## 题目 [机器分配](https://www.acwing.com/problem/content/1015/)

![[image-228fd75e.png]]

## 思路分析

![[image-59365c70.png]]

## 代码实现

```cpp
#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-冲刺国赛]] ➡️ [[金明的预算方案|金明的预算方案]]