公司网站公司哪家好,广州cms模板建站,学编程哪个机构有权威,黑龙江建设网教育官网开心的金明 说明 金明今天很开心#xff0c;家里购置的新房就要领钥匙了#xff0c;新房里有一间他自己专用的很宽敞的房间。 更让他高兴的是#xff0c;妈妈昨天对他说#xff1a;“你的房间需要购买哪些物品#xff0c;怎么布置#xff0c;你说了算#xff0c;只要不超… 开心的金明 说明 金明今天很开心家里购置的新房就要领钥匙了新房里有一间他自己专用的很宽敞的房间。 更让他高兴的是妈妈昨天对他说“你的房间需要购买哪些物品怎么布置你说了算只要不超过N元钱就行”。 今天一早金明就开始做预算但是他想买的东西太多了肯定会超过妈妈限定的N元。 于是他把每件物品规定了一个重要度分为5等用整数1~5 表示第5等最重要。 他还从因特网上查到了每件物品的价格都是整数元。 他希望在不超过N元可以等于N元的前提下使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]重要度为w[j]共选中了k件物品编号依次为j1j2……jk则所求的总和为v[j1]*w[j1]v[j2]*w[j2]…v[jk]*w[jk] 。其中*为乘号 请你帮助金明设计一个满足要求的购物单。 输入格式 输入的第1行为两个正整数用一个空格隔开N m其中N(30000表示总钱数m25为希望购买物品的个数。 从第2行到第m1行第j行给出了编号为j−1的物品的基本数据每行有2个非负整数v p其中v表示该物品的价格(v10000)p表示该物品的重要度(1~5)) 输出格式 输出只有一个正整数为不超过总钱数的物品的价格与重要度乘积的总和的最大值100000000。 样例 输入数据 1 1000 5
800 2
400 5
300 5
400 3
200 2 Copy 输出数据 1 3900 Copy 提示
NOIP 2006 普及组 第二题
#includebits/stdc.h
using namespace std;
int q,w,e,r,t,y,u,o,p,s,d,f,g,h,j,l,z,x,c,v,n,m,i,k,a[100],aa[100],aaa[100],b[100][30010],bb[100][100];
int main()
{cinmn;for(i1;in;i){cina[i]aa[i];}for(i1;in;i){for(j0;jm;j){b[i][j]b[i-1][j];if(ja[i])b[i][j]max(b[i][j],b[i-1][j-a[i]]a[i]*aa[i]);}}for(i0;im;i){pmax(p,b[n][i]);}coutp;return 0;
}
