java 题目描述:总公司拥有高效设备M台,准备分给下属的N个分公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M≤15,N≤10。分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数M。 输入 输入数据文件格式为:第一行有两个数,第一个数是分公司数N,第二个数是设备台数M。 接下来是一个N*M的矩阵,表明了第I个公司分配J台机器的盈利。 输出 输出第一行是总盈利 然后n行每行2个数,
时间: 2024-02-06 17:11:41 浏览: 123
分别表示第i个分公司获得的设备数量和盈利。如果有多种方案可以使得总盈利最大,输出任意一种即可。
Java代码实现:
```java
import java.util.Scanner;
public class Main {
private static int n; // 分公司数
private static int m; // 设备台数
private static int[][] profit; // 盈利矩阵
private static int[][] dp; // 动态规划矩阵
private static int[][] choice; // 记录决策
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
profit = new int[n][m];
dp = new int[n][m + 1];
choice = new int[n][m + 1];
// 读入盈利矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
profit[i][j] = scanner.nextInt();
}
}
// 动态规划求解
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= j; k++) {
if (i == 0) {
dp[i][j] = Math.max(dp[i][j], profit[i][k]);
} else {
int temp = dp[i - 1][j - k] + profit[i][k];
if (dp[i][j] < temp) {
dp[i][j] = temp;
choice[i][j] = k;
}
}
}
}
}
// 输出结果
System.out.println(dp[n - 1][m]);
int[] machines = new int[n];
for (int i = n - 1, j = m; i >= 0; i--) {
machines[i] = choice[i][j];
j -= choice[i][j];
}
for (int i = 0; i < n; i++) {
System.out.println(machines[i] + " " + profit[i][machines[i]]);
}
}
}
```
这道题可以采用动态规划的思想,设dp[i][j]表示前i个分公司分配j台设备所能获得的最大盈利,那么就有:
dp[i][j] = max(dp[i-1][j-k] + profit[i][k]),其中0 <= k <= j
表示第i个分公司分配k台设备,前i-1个分公司分配j-k台设备所获得的最大盈利加上第i个分公司分配k台设备所能获得的盈利,取其中最大值。
由于每个分公司可以获得任意数量的设备,因此需要枚举分配的设备数量k。同时,需要记录决策,即第i个分公司分配了多少台设备,以便后续输出方案。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)