分组背包问题与背包问题求具体方案(二)

简介: AcWing算法提高课内容,本文讲解 动态规划

机器分配

题目要求

题目描述:

总公司拥有 M 台相同的高效设备,准备分给下属的 N  个分公司。


各分公司若获得这些设备,可以为国家提供一定的盈利。盈利与分配的设备数量有关。


问:如何分配这 M  台设备才能使国家得到的盈利最大?


求出最大盈利值。


分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数 M 。

输入格式:

第一行有两个数,第一个数是分公司数 N,第二个数是设备台数 M ;

接下来是一个 N ∗ M  的矩阵,矩阵中的第 i 行第 j  列的整数表示第 i 个公司分配 j台机器时的盈利。

输出格式:

第一行输出最大盈利值;

接下 N  行,每行有 2  个数,即分公司编号和该分公司获得设备台数。

答案不唯一,输出任意合法方案即可。

数据范围:

1N10,

1M15

输入样例:

3 3
30 40 50
20 30 50
20 25 30

输出样例:

70
1 1
2 1
3 1

思路分析

可以看做分组背包问题:即每个公司分配的设备数是唯一的,并且要求具体的分配方案,即:背包问题求具体方案;这里其实有两种写法,代码一为按照本博客中的题目:背包问题求具体方案 进行倒枚举,但需注意,倒枚举的话输出的应为:f [ 1 ] [ m ],另一种方法就是记录分配过程,这种方法就不需要进行倒枚举。

代码一

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15, M = 20;
int w[N][M];
int f[N][M];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> w[i][j];
    for (int i = n; i >= 1; i -- )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= j; k ++ )
                f[i][j] = max(f[i][j], f[i + 1][j - k] + w[i][k]);
    cout << f[1][m] << endl;   // 注意是 f[1][m]
    int j = m;
    for (int i = 1; i <= n; i ++ )
        for (int k = 0; k <= j; k ++ )
            if (f[i][j] == f[i + 1][j - k] + w[i][k])
            {
                cout << i << ' ' << k << endl;
                j -= k;
                break;
            }
    return 0;
}

代码二

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15, M = 20;
int w[N][M];
int f[N][M];
int ways[N];
int main()
{
    int n, m;
    cin >> n >> m;
    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 ++ )
            for (int k = 0; k <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
    cout << f[n][m] << endl;
    int j = m;
    for (int i = n; i >= 1; i -- )
        for (int k = 0; k <= j; k ++ )
            if (f[i][j] == f[i - 1][j - k] + w[i][k])
            {
                ways[i] = k;
                j -= k;
                break;
            }
    for (int i = 1; i <= n; i ++ )
        cout << i << ' ' << ways[i] << endl;
    return 0;
}

能量石

题目要求

题目描述:

岩石怪物杜达生活在魔法森林中,他在午餐时收集了 N  块能量石准备开吃。

由于他的嘴很小,所以一次只能吃一块能量石。

能量石很硬,吃完需要花不少时间。

吃完第 i 块能量石需要花费的时间为 S i 秒。

杜达靠吃能量石来获取能量。

不同的能量石包含的能量可能不同。

此外,能量石会随着时间流逝逐渐失去能量。

第 i 块能量石最初包含 E i 单位的能量,并且每秒将失去 L i 单位的能量。

当杜达开始吃一块能量石时,他就会立即获得该能量石所含的全部能量(无论实际吃完该石头需要多少时间)。

能量石中包含的能量最多降低至 0 。

请问杜达通过吃能量石可以获得的最大能量是多少?

输入格式:

image.png

输出格式:

每组数据输出一个结果,每个结果占一行。

结果表示为 Case #x: y,其中 x 是组别编号(从 1  开始),y  是可以获得的最大能量值。

数据范围:

image.png

输入样例:

3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0

输出样例:

Case #1: 105
Case #2: 8
Case #3: 500

样例解释:

在样例 #1 中,有N=4个宝石。杜达可以选择的一个吃石头顺序是:

image.png

他一共获得了 105  单位的能量,这是能获得的最大值,所以答案是 105 。

在样本案例 #2 中,有 N=3个宝石。

无论杜达选择吃哪块石头,剩下的两个石头的能量都会耗光。

所以他应该吃第三块石头,给他提供 8 单位的能量。

在样本案例 #3 中,有N=2 个宝石。杜达可以:

image.png

所以答案是 500

思路分析

image.png

memset(f, -0x3f, sizeof f);
f[0] = 0;

这样就能保证我们的每一个状态都是由初始状态转移而来,接下来进入贪心分析:

image.png

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 10010;
struct Stone{
    int s, e, l;
    bool operator < (const Stone &w) const{
        return s * w.l < w.s * l;
    }
}stone[N];
int f[M];
int main()
{
    int T;
    scanf("%d", &T);
    for (int C = 1; C <= T; C ++ )
    {
        int n;
        scanf("%d", &n);
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        int m = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int s, e, l;
            scanf("%d%d%d", &s, &e, &l);
            stone[i] = {s, e, l};
            m += s;
        }
        sort(stone + 1, stone + 1 + n);
        for (int i = 1; i <= n; i ++ )
            for (int j = m; j; j -- )
            {
                int s = stone[i].s, e = stone[i].e, l = stone[i].l;
                if (j >= s) f[j] = max(f[j], f[j - s] + max(0, e - (j - s) * l));
            }
        int res = 0;
        for (int i = 1; i <= m; i ++ ) res = max(res, f[i]);
        printf("Case #%d: %d\n", C, res);
    }
    return 0;
}










目录
相关文章
|
6月前
多重背包问题
多重背包问题
57 0
|
6月前
多重背包和分组背包
多重背包和分组背包
|
1月前
|
C语言
末谈背包问题求具体方案
末谈背包问题求具体方案
|
算法 C语言 C++
【动态规划】多重背包问题,分组背包问题
与完全背包问题不同的是,每种东西都是有限件,前两种状态就不再过多赘述
147 4
动态规划——多重背包、分组背包
动态规划——多重背包、分组背包
61 0
|
算法 C++
|
算法
分组背包问题与背包问题求具体方案(一)
AcWing算法提高课内容,本文讲解 动态规划
191 0
分组背包问题与背包问题求具体方案(一)
多重背包问题与优化(裸题)(一)
多重背包问题与优化(裸题)
124 0
多重背包问题与优化(裸题)(一)