当前位置：首页 > news >正文

动态规划——机器分配、01背包问题

news 来源：原创 2025/7/5 16:59:42

一、机器分配

题目名称：机器分配
题目描述：
总公司拥有高效设备M台，准备分给下属的N个分公司。
各分公司若获得这些设备，可以为国家提供一定的盈利。
问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。
其中M≤100，N≤100。
分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

输入输出格式

输入格式：
第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；
接下来是一个N*M的矩阵，表明了第 I 个公司分配 J 台机器的盈利。

输出格式：
第一行输出最大盈利值；接下N行，每行有2个数，即分公司编号和该分公司获得设备台数。

（一）解题思路

1. 问题定义

总公司有n个分公司，现在有m台设备可以分配给这些分公司。每个分公司i如果得到j台设备，会产生一定的盈利a[i][j]。任务是找到一个分配方案，使得所有分公司获得的盈利总和最大。

2. 动态规划的基本思想

动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它通常用于优化问题，比如求最大值或最小值。在这个问题中，我们使用动态规划来找到最大的盈利总和。

3. 状态定义

我们定义一个二维数组f，其中f[i][j]表示前i个分公司分配j台设备时的最大盈利。注意，这里我们是从1开始索引的，所以f[1][0]表示第一个分公司没有分配到设备时的盈利（通常是0，因为没有设备就没有盈利）。

4. 状态转移方程

对于每个分公司i和每个可能的设备数量j，我们需要考虑把k台设备（其中0 <= k <= j）分配给分公司i，然后看看这样分配是否会比之前的分配方案产生更多的盈利。我们可以使用以下状态转移方程来更新f[i][j]：

f[i][j] = max(f[i][j], f[i-1][j-k] + a[i][k])

这里，f[i-1][j-k]表示前i-1个分公司分配j-k台设备时的最大盈利，a[i][k]表示第i个分公司分配k台设备时的盈利。我们通过遍历所有可能的k值来找到使f[i][j]最大的那个。

5. 记录路径

为了能够在找到最大盈利后回溯出具体的设备分配方案，我们需要一个额外的二维数组res来记录每个状态f[i][j]是如何达到的。具体来说，res[i][j]应该存储分配给分公司i的设备数量k，这个k是在计算f[i][j]时使盈利最大的那个。

6. 初始化

我们需要初始化f数组和res数组。通常，我们会把f数组的所有元素初始化为一个很小的值（表示还没有计算过），然后把f[0][0]初始化为0（表示没有分公司和没有设备时的盈利为0）。在这个问题中，由于盈利是非负的，并且我们总是试图最大化盈利，所以我们可以简单地把f数组的所有元素（除了f[0][0]）看作是未初始化的，然后在计算过程中更新它们。res数组也需要初始化，但在这个问题中，我们只需要在更新f[i][j]的同时也更新res[i][j]即可。

7. 回溯

一旦我们计算出了f[n][m]（即所有分公司分配所有设备时的最大盈利），我们就可以使用res数组来回溯出具体的设备分配方案。我们从f[n][m]开始，根据res[n][m]找到分配给最后一个分公司的设备数量，然后递归地找到分配给前面分公司的设备数量，直到我们回溯到f[1][0]（或实际上是我们开始回溯的第一个有效状态）。

（二）代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 30
#define MOD 2520
#define E 1e-12
using namespace std;int a[N][N], f[N][N], res[N][N]; void print(int x, int y) {if (x == 0)return;print(x - 1, y - res[x][y]);printf("%d %d\n", x, res[x][y]);
}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 = 1; j <= m; j++) for (int k = 0; k <= j; k++) if (f[i][j] <= f[i-1][j-k] + a[i][k]) {f[i][j] = f[i-1][j-k] + a[i][k];res[i][j] = k; }// 输出结果cout << f[n][m] << endl;print(n,m);return 0;
}

二、01背包问题

描述

一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，…,Wn,它们的价值分别为C1,C2,…,Cn，求旅行者能获得最大总价值。

输入格式

第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；
第2至N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。

输出格式

仅一行，一个数，表示最大总价值。

样例

输入样例

10 4
2 1
3 3
4 5
7 9

输出样例

12

（一）解题思路

问题定义与数据输入
（1）我们需要明确背包的容量m和物品的数量n。
（2）输入每个物品的体积v[i]和价值w[i]（其中i代表物品编号）。
动态规划数组的初始化
（1）定义一个二维数组f[i][j]，其中i代表物品编号（从1到n），j代表当前的背包容量（从0到m）。
（2）f[i][j]表示当只考虑前i个物品，且背包容量为j时，能够获得的最大价值。
（3）初始化f[0][j]为0，表示当没有物品可选时，任何背包容量下的最大价值都是0。
状态转移方程
（1）对于每个物品i和每个可能的背包容量j，我们需要决定是否将该物品放入背包中。
（2）如果不放入物品i，则f[i][j] = f[i-1][j]，即当前最大价值等于前i-1个物品在背包容量为j时的最大价值。
（3）如果放入物品i，则f[i][j] = f[i-1][j-v[i]] + w[i]，但前提是背包容量j必须大于等于物品i的体积v[i]。
（4）因此，状态转移方程为：

f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]) 当j >= v[i]时

f[i][j] = f[i-1][j] 当j<v[i]时

（二）代码

#include <iostream>
using namespace std;const int N = 210;
int n, m; // n表示物体个数，m表示背包容量
int v[N], w[N]; // v[i]表示第i个物品的体积，w[i]表示第i个物品的价值
int f[N][N]; // f[i][j]表示前i个物品在总体积不超过j时的最大价值int main() {cin >> m >> n; // m表示背包容量，n表示物体个数for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i]; // 读入每个物品的体积和价值}// 初始化f数组，f[0][j]表示没有物品可选时，任何体积下的最大价值都是0for (int j = 0; j <= m; j++) {f[0][j] = 0;}// 动态规划求解背包问题for (int i = 1; i <= n; i++) { // 表示只选择前i个物体for (int j = 1; j <= m; j++) { // 表示体积f[i][j] = f[i - 1][j]; // 如果不选第i个物品，则价值等于前i-1个物品在体积j下的最大价值if (j >= v[i]) { // 如果体积允许选择第i个物品f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); // 选择第i个物品，并更新最大价值}}}// 输出结果，表示选择前n个物品，体积为m时的最大价值cout << f[n][m] << endl;return 0;
}

一、机器分配

（一）解题思路

1. 问题定义

2. 动态规划的基本思想

3. 状态定义

4. 状态转移方程

5. 记录路径

6. 初始化

7. 回溯

（二）代码

二、01背包问题

（一）解题思路

（二）代码

相关文章：