acwing算法提高之动态规划--背包模型(三)
2023-12-13 13:32:24
1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1:潜水员。
解题思路:DP。
状态定义f[i][j][k]
:从前i个物品中选,氧气至少为j,氮气至少为k的最小方案数。
状态转移,以下情况的最小值,
- 不选择第i个物品,即
f[i-1][j][k]
。 - 选择第i个物品,即
f[i - 1][j - v1[i]][k - v2[i]] + w[i]
。(状态从i-1层转移过来的,故从大到小循环。)
同样地,可以将状态优化到二维。
初始化,f[i][j] = 0x3f3f3f3f
,f[0][0] = 0
。
最终答案,返回f[n][m]
。
C++代码如下,
#include <iostream>
#include <cstring>
using namespace std;
const int N = 30, M = 90;
int n, m, k;
//n表示氧气需要的量
//m表示氮气需要的量
//k表示气缸的个数
int f[N][M];
int main() {
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
cin >> n >> m >> k;
while (k--) {
int a, b, c;
cin >> a >> b >> c;
for (int i = n; i >= 0; --i) {
for (int j = m; j >= 0; --j) {
f[i][j] = min(f[i][j], f[max(i - a, 0)][max(j - b, 0)] + c);
}
}
}
cout << f[n][m] << endl;
return 0;
}
题目2:背包问题求解具体方案数。
解题思路:求具体方案数不难,关键是求解字典序最小的,有些困难。
C++代码如下,
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
for (int i = n; i >= 1; --i) {
for (int j = 0; j <= m; ++ j) {
f[i][j] = f[i + 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
}
int j = m;
for (int i = 1; i <= n; ++i) {
if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
cout << i << " ";
j -= v[i];
}
}
return 0;
}
题目3:机器分配。
解题思路:分组背包问题求解最大价值和具体方案。
C++代码如下,
#include <iostream>
using namespace std;
const int N = 20;
int n, m;
int w[N][N]; //第i组第k台的价值
int f[N][N];
int s[N]; //第i组选了第多少台
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int k = 1; k <= m; ++k) {
cin >> w[i][k];
}
}
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 <= m; ++k) {
if (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 = 1; k <= m; ++k) {
if (j >= k && f[i][j] == f[i-1][j - k] + w[i][k]) {
s[i] = k;
j -= k;
break;
}
}
}
for (int i = 1; i <= n; ++i) {
cout << i << " " << s[i] << endl;
}
return 0;
}
题目4:金明的预算方案。
解题思路:分组背包问题。
C++代码如下,
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int M = 32010;
int n, m;
int f[M];
int main() {
cin >> m >> n;
//读入n个物品
struct ITEM {
ITEM(int a, int b) : v(a), w(b) {} //构造函数
int v;//体积
int w;//价格
};
vector<ITEM> items;
items.emplace_back(ITEM(-1,-1));
unordered_map<int, vector<int>> son; //son[i]表示物品i的附件们
for (int i = 1; i <= n; ++i) {
int v, p, q;
cin >> v >> p >> q;
ITEM item(v, p * v);
items.emplace_back(item);
if (q == 0) {
//第i件物品是主件
son[i].emplace_back(-1);
son[i].pop_back();
} else {
//第i件物品是附件,它的主件是q
son[q].emplace_back(i);
}
}
//分组背包问题求解
for (auto [i, vec] : son) {
//遍历每一个主件i,和它的附件vec
for (int j = m; j >= 0; --j) {
//考虑每一个附件
for (int k = 0; k < 1 << vec.size(); ++k) {
int v = items[i].v, w = items[i].w;
//遍历每个附件
for (int ii = 0; ii < vec.size(); ++ii) {
if (k >> ii & 1) {
//选择了第ii个附件
v += items[vec[ii]].v;
w += items[vec[ii]].w;
}
}
if (j >= v) f[j] = max(f[j], f[j - v] + w);
}
}
}
cout << f[m] << endl;
return 0;
}
题目5:开心的金明。
解题思路:01背包问题即可。
C++代码如下,
#include <iostream>
using namespace std;
const int M = 30010;
int n, m;
int f[M];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; ++i) {
int v, p;
cin >> v >> p;
int w = v * p;
for (int j = m; j >= v; --j) {
f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[m] << endl;
return 0;
}
文章来源:https://blog.csdn.net/YMWM_/article/details/134911978
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!