宣传一下算法提高课整理 <—
CSDN个人主页：更好的阅读体验 <—
本题链接（AcWing） 点这里
题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。
更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N N N 元钱就行”。
今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N N N 元。
于是，他把每件物品规定了一个重要度，分为 5 5 5 等：用整数 1 ∼ 5 1 \sim 5 1∼5 表示，第 5 5 5 等最重要。
他还从因特网上查到了每件物品的价格（都是整数元）。
他希望在不超过 N N N 元（可以等于 N N N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 j j j 件物品的价格为 v [ j ] v[j] v[j]，重要度为 w [ j ] w[j] w[j]，共选中了 k k k 件物品，编号依次为 j 1 ， j 2 ， … ， j k j_1，j_2，…，j_k j1，j2，…，jk，则所求的总和为：
v [ j 1 ] × w [ j 1 ] + v [ j 2 ] × w [ j 2 ] + … + v [ j k ] × w [ j k ] v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+…+v[j_k] \times w[j_k] v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]
请你帮助金明设计一个满足要求的购物单。
输入格式
输入文件的第 1 1 1 行，为两个正整数 N N N 和 m m m，用一个空格隔开。（其中 N N N 表示总钱数， m m m 为希望购买物品的个数）
从第 2 2 2 行到第 m + 1 m+1 m+1 行，第 j j j 行给出了编号为 j − 1 j-1 j−1 的物品的基本数据，每行有 2 2 2 个非负整数 v v v 和 p p p。（其中 v v v 表示该物品的价格， p p p 表示该物品的重要度）
输出格式
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（数据保证结果不超过 1 0 8 10^8 108）。
数据范围
1
≤
N
<
30000
1 \le N < 30000
1≤N<30000,
1
≤
m
<
25
1 \le m < 25
1≤m<25,
0
≤
v
≤
10000
0 \le v \le 10000
0≤v≤10000,
1
≤
p
≤
5
1 \le p \le 5
1≤p≤5
输入样例：
1000 5
800 2
400 5
300 5
400 3
200 2
输出样例：
3900
思路
其实就是 01背包问题 。
详见注释。
AC Code:
C + + C++ C++
#include <iostream>
using namespace std;
const int N = 30010;
int n, m;
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++ )
{
int v, p;
cin >> v >> p;
for (int j = n; j >= v; j -- )
f[j] = max(f[j], f[j - v] + v * p); // 01背包问题，把价值定为 v * p
}
cout << f[n] << endl;
return 0;
}
文章来源：https://www.toymoban.com/news/detail-476067.html
最后，如果觉得对您有帮助的话，点个赞再走吧！文章来源地址https://www.toymoban.com/news/detail-476067.html
到了这里，关于AcWing算法提高课-1.3.14开心的金明的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
