河北网站建设制作,logo设计哪里做得好,怎么阻止网站,wordpress扫码验证下载[NOIP2006 普及组] 开心的金明
题目描述
金明今天很开心#xff0c;家里购置的新房就要领钥匙了#xff0c;新房里有一间他自己专用的很宽敞的房间。更让他高兴的是#xff0c;妈妈昨天对他说#xff1a;“你的房间需要购买哪些物品#xff0c;怎么布置#xff0c;你说…[NOIP2006 普及组] 开心的金明
题目描述
金明今天很开心家里购置的新房就要领钥匙了新房里有一间他自己专用的很宽敞的房间。更让他高兴的是妈妈昨天对他说“你的房间需要购买哪些物品怎么布置你说了算只要不超过 N N N元钱就行”。今天一早金明就开始做预算但是他想买的东西太多了肯定会超过妈妈限定的 N N N元。于是他把每件物品规定了一个重要度分为 5 5 5等用整数 1 − 5 1-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]。
请你帮助金明设计一个满足要求的购物单。
输入格式
第一行为 2 2 2个正整数用一个空格隔开 n , m n,m n,m其中 N ( 30000 ) N(30000) N(30000)表示总钱数 m ( 25 ) m(25) m(25)为希望购买物品的个数。
从第 2 2 2行到第 m 1 m1 m1行第 j j j行给出了编号为 j − 1 j-1 j−1的物品的基本数据每行有 2 2 2个非负整数$ v p 其中 其中 其中v 表示该物品的价格 表示该物品的价格 表示该物品的价格(v \le 10000) p$表示该物品的重要度( 1 − 5 1-5 1−5)
输出格式 1 1 1个正整数为不超过总钱数的物品的价格与重要度乘积的总和的最大值 ( 100000000 ) (100000000) (100000000)。
样例 #1
样例输入 #1
1000 5
800 2
400 5
300 5
400 3
200 2样例输出 #1
3900提示
NOIP 2006 普及组 第二题 思路
假设现在已经处理了前i个物品总共还剩下j元钱可以用于购买物品那么在这个条件下我们可以获得的最大的物品价值是多少
使用了一个二维数组dp[i][j]表示到第i个物品总价值超过j的最大收益。其中i表示物品编号j表示当前的总钱数。最终程序输出的是dp[m][n]也就是到第m个物品总钱数为n时可以获得的最大价值。
使用了两个for循环第一个循环是对于每个物品的循环第二个循环是对于钱数的循环。在每个循环中如果当前的钱数不够买当前的物品那么我们就不买这个物品直接继承上一个物品的最大价值。否则我们可以选择买或不买当前的物品选择买或不买的原则是买当前的物品能够获得更多的价值就买否则就不买。这一步用到了max()函数。 AC代码
#include iostream
#include algorithm
#define AUTHOR HEX9CF
using namespace std;const int maxn 100005;// 到第i个物品总价值超过j的最大收益
int dp[30][maxn];int main()
{// 总钱数、个数int n, m;// 价格、重要度int v[30], w[30];cin n m;for (int i 1; i m; i){cin v[i] w[i];}for (int i 1; i m; i){for (int j 0; j n; j){if(j v[i]) {// 不够钱不买dp[i][j] dp[i - 1][j];} else {dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] v[i] * w[i]);}}}cout dp[m][n] endl;return 0;
}
