「背包DP」合唱队形
本题为3月16日23上半学期集训每日一题中A题的题解
题面
题目描述
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1−5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为 \(v_j\) ,重要度为 \(w_j\) ,共选中了k件物品,编号依次为 \(j_1,j_2,\cdots,j_k\) ,则所求的总和为:\(v_{j_1} \times w_{j_1} + v_{j_2} \times w_{j_2} + \cdots + v_{j_k} \times w_{j_k}\).
请你帮助金明设计一个满足要求的购物单。
输入
第一行,为2个正整数,用一个空格隔开:N m(其中N (<30000)表示总钱数,m(<25)为希望购买物品的个数。)
从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有2个非负整数v p(其中v表示该物品的价格( \(v \leq 10000\) ),p表示该物品的重要度(1−5).
输出
1个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。
样例输入
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出
3900
思路分析
本题就是一个最基础的01背包
的模型,只是此处每个商品的价值被定义为它的 \(价格 \times 优先级\) 而已,所以直接套用01背包
的板子即可.
此处 $ N \times m < 750000$ ,故无需进行空间压缩,使用普通的01背包
板子即可.当然你想空间压缩也是可行的.
如果你还不会01背包
,请先阅读背包九讲(如果打不开github也可以在集训队的群文件中搜索),或者这篇博客(可能需要一点魔法才能访问)进行学习,当然也可自行搜索博客等学习.在ACWing上有公开的01背包的板子题,请尝试独立通过此题,然后再来做这道题.
参考代码
时间复杂度: \(O(NM)\)
空间复杂度: \(O(NM)\)
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
int *v = new int[m + 1]; // 价格
int *p = new int[m + 1]; // 优先级
for (int i = 1; i <= m; i++) {
cin >> v[i] >> p[i];
}
// 背包DP模板
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (j - v[i] >= 0) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i] * p[i]); // 此题中每个商品的价值是它的价格乘优先级
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[m][n] << "\n";
return 0;
}
"正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯" ---亚里士多德
这里是浙江理工大学22届ACM集训队的成员一枚鸭!
本文首发于博客园,作者:星双子,除了我自己的转载请注明原文链接:https://www.cnblogs.com/geministar/p/zstu23_3_16_A.html