本题为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 (
从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有2个非负整数v p(其中v表示该物品的价格( (v leq 10000) ),p表示该物品的重要度(1−5).
输出
1个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(
样例输入
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出
3900
思路分析
本题就是一个最基础的01背包
的模型,只是此处每个商品的价值被定义为它的 (价格 times 优先级) 而已,所以直接套用01背包
的板子即可.
此处 $ N times m 01背包板子即可.当然你想空间压缩也是可行的.
如果你还不会01背包
,请先阅读背包九讲(如果打不开github也可以在集训队的群文件中搜索),或者这篇博客(可能需要一点魔法才能访问)进行学习,当然也可自行搜索博客等学习.在ACWing上有公开的01背包的板子题,请尝试独立通过此题,然后再来做这道题.
参考代码
时间复杂度: (O(NM))
空间复杂度: (O(NM))
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include
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 > v[i] >> p[i];
}
// 背包DP模板
vector> dp(m + 1, vector(n + 1));
for (int i = 1; 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
“正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯” —亚里士多德
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net