机器分配

题目

链接：https://www.acwing.com/problem/content/1015/

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

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

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

求出最大盈利值。

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

输入格式

第一行有两个数，第一个数是分公司数 $N$，第二个数是设备台数 $M$；

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

输出格式

第一行输出最大盈利值；

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

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

数据范围

$1 \le N \le 10$,
$1 \le M \le 15$

输入样例：

3 3
30 40 50
20 30 50
20 25 30

输出样例：

70
1 1
2 1
3 1

思路

将本题转换为分组背包问题：

分组背包问题：

有 $N$ 组物品和一个容量是 $V$ 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号，$j$ 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

思路：

状态表示：f[i][j]表示前i组物品，能放入容量为j的背包的最大价值

循环物品组，循环背包容量，对于第i组物品，容量为j的背包，有s+1种选法，取最大值

• 将每家公司看成一个物品组，
• 分给第i个公司的不同机器数量可以分别看成一个物品组内的物品，即要么选0台，1台，，，m台，一定是这些选法里面的一种

动态规划：

• 状态表示：f[i][j]表示考虑前i个物品组，选法的总体积不超过j的方案的收益最大值

• 状态计算：集合划分：考虑前i个公司给多少个机器

• • 不选或者选不了：f[i-1][j]
  • 选 第i个物品：f[i-1][j-k]+w[i][k]

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

int n, m;
int w[20][20];
int f[20][20]; //从前i个物品中选，总体积不超过j的方案的最大值
int path[20];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    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++) {
            f[i][j] = f[i - 1][j];//不选;
            for (int k = 1; 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]) {
                path[i] = k;
                j -= k;
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << i << ' ' << path[i] << endl;
    }
    return 0;
}

金明的预算方案

题目

链接：https://www.acwing.com/problem/content/489/

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。

今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

QQ截图20190313024710.png

如果要买归类为附件的物品，必须先买该附件所属的主件。

每个主件可以有0个、1个或2个附件。

附件不再有从属于自己的附件。

金明想买的东西很多，肯定会超过妈妈限定的N元。

于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。

他还从因特网上查到了每件物品的价格（都是10元的整数倍）。

他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为$j_1，j_2，…，j_k$，则所求的总和为：

$v[j_1] * w[j_1]+v[j_2] * w[j_2]+…+v[j_k] * w[j_k]$ （其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

输入格式

输入文件的第1行，为两个正整数，用一个空格隔开：N m，其中N表示总钱数，m为希望购买物品的个数。

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q，其中v表示该物品的价格，p表示该物品的重要度（1~5），q表示该物品是主件还是附件。

如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号。

输出格式

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

数据范围

$N < 32000, m < 60, v < 10000$ $N < 32000, m < 60, v < 10000$

输入样例：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出样例：

2200

思路

可以将本题转换为分组背包问题：

主物品：代表多少组

附件：划分一个组中多少个物品

例如 2个附件 a1,a2,一个主物品c

• 可以组成： c | c,a1 | c,a2 | c,a1,a2

每个组中的划分只能用其中的一个

求出对应组的每个划分块需要多少钱（体积），钱*重要程度（相当于价值）

可以使用二进制枚举的方式，来计算附件选哪几件：

for (int k = 0; k < 1 << cxk.size(); k++) {
    int v = master[i].first, w = master[i].second; //体积，价值
    for (int u = 0; u < cxk.size(); u++) {
        if (k >> u & 1) { //1代表选
            v += cxk[u].first;
            w += cxk[u].second;
        }
    }
    if (j >= v) {
        f[j] = max(f[j], f[j - v] + w);
    }
}

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;
typedef pair<int, int> PII;

vector<PII> master(100);
vector<PII> servent[100];
int f[32010];
int n, m;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int v, p, q;
        cin >> v >> p >> q;
        if (q == 0) master[i] = {v, v * p};
        else servent[q].push_back({v, v * p});
    }

    for (int i = 1; i <= n; i++) {
        if (master[i].first) { //是主件
            for (int j = m; j >= 0; j--) {
                vector<PII> cxk = servent[i]; //所有附件
                for (int k = 0; k < 1 << cxk.size(); k++) {
                    int v = master[i].first, w = master[i].second; //体积，价值
                    for (int u = 0; u < cxk.size(); u++) {
                        if (k >> u & 1) {
                            v += cxk[u].first;
                            w += cxk[u].second;
                        }
                    }
                    if (j >= v) {
                        f[j] = max(f[j], f[j - v] + w);
                    }
                }
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

开心的金明

题目：

链接：https://www.acwing.com/problem/content/428/

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。

今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $N$ 元。

于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1 \sim 5$ 表示，第 $5$ 等最重要。

他还从因特网上查到了每件物品的价格（都是整数元）。

他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v[j]$，重要度为 $w[j]$，共选中了 $k$ 件物品，编号依次为 $j_1，j_2，…，j_k$，则所求的总和为：

$$v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+…+v[j_k] \times w[j_k]$$

请你帮助金明设计一个满足要求的购物单。

输入格式

输入文件的第 $1$ 行，为两个正整数 $N$ 和 $m$，用一个空格隔开。（其中 $N$ 表示总钱数，$m$ 为希望购买物品的个数）

从第 $2$$2$ 行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v$ 和 $p$。（其中 $v$ 表示该物品的价格，$p$ 表示该物品的重要度）

输出格式

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（数据保证结果不超过 $10^8$）。

数据范围

$1 \le N < 30000$,
$1 \le m < 25$,
$0 \le v \le 10000$,
$1 \le p \le 5$

输入样例：

1000 5
800 2
400 5
300 5
400 3
200 2

输出样例：

3900

思路

01背包问题：

状态计算：f[i][j]表示所有从前i个物品选，且总体积不超过j的选法集合中的价值最大值

集合划分：

• 按照第i种物品选或者不选划分 f[i][j]集合。

• 不选第i种物品,f[i][j] = f[i-1][j];

• • 问题转化为从前i-1个物品选，且总体积不超过j的选法集合中的最大值。

• 选第i种物品, f[i][j] = f[i-1][j-v] + v*w ;

• • 已经确定选第i种物品，那么问题转化为从前i-1个物品选，且总体积不超过j-v的选法集合中的最大值再加上 v*w。

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> m >> n;
    vector<int> f(m + 1);
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        int v = a, w = b * a;
        for(int j=m;j>=v;j--)
            f[j]= max(f[j],f[j-v]+w);
    }
    cout<<f[m]<<endl;     
  	return 0;
}

货币系统

题目

链接：https://www.acwing.com/problem/content/1023/

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

输入格式

第一行，包含两个整数n和m。

接下来n行，每行包含一个整数，表示一种货币的面值。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

$n≤15,m≤3000$

输入样例：

3 10
1
2
5

输出样例：

10

思路

这是一个完全背包求方案数的模版

完全背包问题：

动态规划：

状态表示：f[i,j]表示所有从前i个物品中选，且总体积恰好是j的方案

状态计算：

• f[i,j] = f[i-1,j]+f[i-1,j-v*1]+f[i-1.j-v*2]+...+f[i-1,j-v*s]
• f[i,j-v]= f[i-1,j-v*1]+f[i-1,j-v*2]+...+f[i-1,j-v*s]

可以得出：f[i,j]=f[i-1,j]+f[i,j-v]

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> f(m + 1);
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        for (int j = x; j <= m; j++) {
            f[j] += f[j - x];
        }
    }
    cout<<f[m]<<endl;

    return 0;
}

货币系统2

题目

链接：https://www.acwing.com/problem/content/534/

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$，你可以假设每一种货币都有无穷多张。

为了方便，我们把货币种数为 $n$$n$、面额数组为 $a[1..n]$ 的货币系统记作 $(n,a)$。

在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出，即对每一个非负整数 $x$，都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i] × t[i]$ 的和为 $x$。

然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 $x$ 不能被该货币系统表示出。

例如在货币系统 $n=3, a=[2,5,9]$ 中，金额 $1,3$ 就无法被表示出来。

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意非负整数 $x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。

他们希望找到一个货币系统 $(m,b)$，满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价，且 $m$ 尽可能的小。

他们希望你来协助完成这个艰巨的任务：找到最小的 $m$。

输入格式

输入文件的第一行包含一个整数 $T$，表示数据的组数。

接下来按照如下格式分别给出 $T$ 组数据。

每组数据的第一行包含一个正整数 $n$。

接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$。

输出格式

输出文件共有 $T$ 行，对于每组数据，输出一行一个正整数，表示所有与 $(n,a)$ 等价的货币系统 $(m,b)$ 中，最小的 $m$。

数据范围

$1 \le n \le 100$,
$1 \le a[i] \le 25000$,
$1 \le T \le 20$

输入样例：

2 
4 
3 19 10 6 
5 
11 29 13 19 17 

输出样例：

2
5

思路

完全背包问题：求极大无关向量组的个数
我们会发现，所有能被其他货币表示出来的货币都可以被删除，那么这样就可以直接做了，直接把能被其他表示出来的去除即可。

可以先将这个序列排序，然后从小的数开始去晒掉大的数。

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    std::sort(a.begin() + 1, a.end());
    vector<int> f(a[n] + 1);
    f[0] = 1; //当前体积为j的所有方案。
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (f[a[i]]) continue;
        ans++;
        for (int j = a[i]; j <= a[n]; j++) {
            f[j] |= f[j - a[i]];
        }
    }
    cout << ans << endl;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int _;
    cin >> _;
    while (_--) solve();
    return 0;
}

能量石

题目

链接：https://www.acwing.com/problem/content/736/

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

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

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

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

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

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

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

第 $i$ 块能量石最初包含 $E_i$ 单位的能量，并且每秒将失去 $L_i$ 单位的能量。

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

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

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

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $N$，表示能量石的数量。

接下来 $N$ 行，每行包含三个整数 $S_i,E_i,L_i$。

输出格式

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

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

数据范围

$1 \le T \le 10$,
$1 \le N \le 100$,
$1 \le S_i \le 100$,
$1 \le E_i \le 10^5$,
$0 \le L_i \le 10^5$

输入样例：

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$ 个宝石。杜达可以选择的一个吃石头顺序是：

• 吃第四块石头。这需要 $5$ 秒，并给他 $80$ 单位的能量。
• 吃第二块石头。这需要 $5$ 秒，并给他 $5$ 单位的能量（第二块石头开始时具有 $30$ 单位能量，$5$ 秒后失去了 $25$ 单位的能量）。
• 吃第三块石头。这需要 $100$ 秒，并给他 $20$ 单位的能量（第三块石头开始时具有 $30$ 单位能量，$10$ 秒后失去了 $10$ 单位的能量）。
• 吃第一块石头。这需要 $20$ 秒，并给他 $0$ 单位的能量（第一块石头以 $10$ 单位能量开始，$110$ 秒后已经失去了所有的能量）。

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

在样本案例＃2中，有 $N = 3$ 个宝石。

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

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

在样本案例＃3中，有 $N = 2$ 个宝石。杜达可以：

• 吃第一块石头。这需要 $12$ 秒，并给他 $300$ 单位的能量。
• 吃第二块石头。这需要 $5$ 秒，并给他 $200$ 单位的能量（第二块石头随着时间的推移不会失去任何能量！）。

所以答案是 $500$。

思路

对于两个能量石$i,j$来说，如果他们交换之后对答案的贡献不增加，那么应该满足：

• $e_i+e_j-s_i*l_j>=e_j+e_i-s_j*l_i$

化简得：

$s_j*l_i>=s_i*l_j$

因此我们可以按照这个顺序对所有的能量石进行排序，贪心的拿最优的方案。

每个能量石都是拿与不拿的选择，那么这就是一个01背包问题了：

状态表示：f[i,j]表示所有只从前i块能量石中选，且总体积不超过j的方案的最大值

状态计算：f[i,j]=max(f[i-1,j],f[i-1,j-s]+e-(j-s)*L)

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

typedef struct node {
    int s, e, l;
    bool operator<(const node cxk) const {
        return s * cxk.l < cxk.s * l;
    }
} node;

int solve() {
    int n;
    cin >> n;
    vector<node> a(n + 1);
    int m = 0;
    for (int i = 1; i <= n; i++) {
        int s, e, l;
        cin >> s >> e >> l;
        a[i] = {s, e, l};
        m += s;
    }
    std::sort(a.begin() + 1, a.end());
    vector<int> f(m + 1, -0x3f3f3f3f);
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        int s = a[i].s, e = a[i].e, l = a[i].l;
        for (int j = m; j >= s; j--) {
            f[j] = max(f[j], f[j - s] + e - (j - s) * l);
        }
    }
    int res=0;
    for(int i=0;i<=m;i++) res= max(res,f[i]);
    return res;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        std::printf("Case #%d: %d\n",i, solve());
    }
    return 0;
}