主题： http://ACM.nyist.net/judge online/problem.PHP？ pid=49开心微笑乌龟时间限制： 1000ms |内存限制： 65535KB难易度： 4笑容乌龟今天很开心。 家里买的新房要钥匙。 新建的房间有他专用的宽敞房间。 更令人高兴的是，妈妈昨天告诉了他。 “你的房间需要买什么样的？ 需要怎么配置？ 我说过了吧。 只要不超过n元就可以了”。 今天一大早就开始给微笑的乌龟精打细算了，但是他想买的东西太多了，大概会超过妈妈限定的n元吧。 于是，他对每个物品规定了重要度，分为5等。 用整数1~5表示，5等是最重要的。 他还从网上查了各种物品的价格。 他希望在不超过n元(可以等于n元)的前提下，将各物品的价格和重要度之积的总和最大化。 设第j个物品的价格为v[j]，重要度为w[j]，合计选择k个物品，将编号依次设为j1.jk，则求出的合计为v[j1]*w[j1] . v[jk]*w[jk] 帮我金明设计满足要求的购物清单。 请在第一行输入
每个组的测试数据输入的第一行是两个正整数，用一个空格分隔。
纳米
(其中n(30000 )表示总金额，m ) 25 )是希望购买的物品的个数。 ）
从第2行到第m 1行，第j行被编号为j-1
的项的基本数据，每行有两个非负整数
贵宾
(这里，v表示该物品的价格(v10000 )，p表示该物品的重要度)1~5) )每个测试数据的输出组只有一个正整数，是不超过总额的物品的价格和重要度之积的总和
最大值(100000000 )样品输入11000 5800 2400 5300 5400 3200 2样品输出3900
很明显是动态规划问题。 最佳子结构。
a[i][j]=max{a[i-1][j]，v[i]*w[i] a[i-1][j-v[j]]}； 你可以在后台做。 # includeiostreamusingnamespacestd； const int Max=26； //高兴地微笑的乌龟int N，w[Max]，v[Max]，vmax，a[Max][30001]； inlineintmaxx(inta，int b ) {return ab？ a:b； (}int main ) ) {int n； cinn； cin.clear (； cin.sync (； wile(n----) {cinvmaxN； int i，j； for(I=1； i=N； I ) cinv[i]w[i]； for(I=0； i=N； I ) for ) j=0； j=N； j ) a(I ) ) j )=0； for(I=1； i=N； I ) (/I个项目for ) j=1； j=vmax； j ) ) /当前背包容量JIF(v[I]j ) a[I] ) j )=a[I-1][j]； elsea[i][j]=maxx(a[i-1][j]，v[i]*w[i] a[i-1][j-v[i]] )； }}couta[N][vmax]endl； }return 0； }