开心的小明。。。求算法思路，望大神指点一下，谢谢

小明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早小明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。

于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。 他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：

v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）

请你帮助小明设计一个满足要求的购物单。

函数：void GetResult(int*p,int& Get_Result)
    
    输入参数：int*p 指向二维数组的首地址，该二维数组第0行的两个数分别表示：总钱数<30000，和希望购买物品的个数<25;该数组从第1行到第m行(1<=j<=m)中给出了编号为j的物品的基本数据，每行有2个非负整数，表示该物品的价格(<=10000)和该物品的重要度(1~5)。<>  

 Get_Result表示不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。

输出：无 


我能想到的就是把所有的可能都算出来，然后选出一个最大值，这应该是最笨的一种办法了。。大家有没有好的想法，请教一下，谢谢！！

11 个解决方案

#1

这不是典型的线性规划吗, 最常用的算法应该是单纯形法

#2

顶一下

#3

百度：“背包问题”。完结。

#4

这是01背包吧，多了个要记录选择物品 下午回过一直不成功

#5

从现实角度来看，怎么会有人买个东西弄的这么蛋疼，肯定强迫症患者晚期0.0

#6

首选需要对所有物品的重要度*价格的乘积进行排序，由于你并没有明确每样东西的价格和重要度，所以我假设j1到jk是按照重要度*价格降序排列的。
这时问题变成j1到jk要尽可能的多，并且价格总和不能超过某个值（本题里是30000）。
j1到jk要尽可能的多的同时还要压制价格，那么每样东西的数量只可能是1，因为数量多并不能帮助你提升重要度*价格的总和。
这时你只要计算v1+v2+……vn，让他最接近30000就行了（注意这里的v1是j1到jk排序后的j1里的v1）。

#7

引用 6 楼 Raffin 的回复:

首选需要对所有物品的重要度*价格的乘积进行排序，由于你并没有明确每样东西的价格和重要度，所以我假设j1到jk是按照重要度*价格降序排列的。
这时问题变成j1到jk要尽可能的多，并且价格总和不能超过某个值（本题里是30000）。
j1到jk要尽可能的多的同时还要压制价格，那么每样东西的数量只可能是1，因为数量多并不能帮助你提升重要度*价格的总和。
这时你只要计算v1+v2+……vn，让他最接近30000就行了（注意这里的v1是j1到jk排序后的j1里的v1）。

好像单样物品价格很高时这么算有问题，加上这件物品价格会超，如果去掉这件物品又不是最优解。希望有高人修正补充。

#8

补充下，先根据j1到jk排序
然后计算v1到vk，取最接近价格总和的，如果v1加到v(n-1)超过了价格总和，则跳过v(n-1)，继续累加vn，直到遍历到k。

物品1：重要度3，价格500，乘积1500
物品2：重要度4，价格100，乘积400
物品3：重要度1，价格1000，乘积1000
物品4：重要度4，价格300，乘积1200
物品5：重要度2，价格400，乘积800

排序后是物品1，物品4，物品3，物品5，物品2，假设总价格不能超过1000元。
按照这个排序，价格分别是500元，100元，1000元，300元，400元。
那么最优解就是500+100+300，即900元，也就是物品1，物品4和物品5，重要度*价格乘积最大，达到3500。

#9

引用 8 楼 Raffin 的回复:

补充下，先根据j1到jk排序
然后计算v1到vk，取最接近价格总和的，如果v1加到v(n-1)超过了价格总和，则跳过v(n-1)，继续累加vn，直到遍历到k。

物品1：重要度3，价格500，乘积1500
物品2：重要度4，价格100，乘积400
物品3：重要度1，价格1000，乘积1000
物品4：重要度4，价格300，乘积1200
物品5：重要度2，价格400，乘积800

排序后是物品1，物品4，物品3，物品5，物品2，假设总价格不能超过1000元。
按照这个排序，价格分别是500元，100元，1000元，300元，400元。
那么最优解就是500+100+300，即900元，也就是物品1，物品4和物品5，重要度*价格乘积最大，达到3500。

我当时做这道题的时候也是这么想的，但是发现实际中不能这么做，因为有可能会出现以下情况：
剩余钱数：1000
物品1：重要度4，价格1000，乘积4000
物品2：重要度5，价格400，乘积2000
物品3：重要度5，价格500，乘积2500
排序应该是物品1>物品3>物品2
按你的方法是购买物品1
但明显应该购买物品3+物品2利益最大

所以还是老老实实应用单纯形法好了。。。

#10

引用 9 楼 qq_25645261 的回复:

Quote: 引用 8 楼 Raffin 的回复:

补充下，先根据j1到jk排序
然后计算v1到vk，取最接近价格总和的，如果v1加到v(n-1)超过了价格总和，则跳过v(n-1)，继续累加vn，直到遍历到k。

物品1：重要度3，价格500，乘积1500
物品2：重要度4，价格100，乘积400
物品3：重要度1，价格1000，乘积1000
物品4：重要度4，价格300，乘积1200
物品5：重要度2，价格400，乘积800

排序后是物品1，物品4，物品3，物品5，物品2，假设总价格不能超过1000元。
按照这个排序，价格分别是500元，100元，1000元，300元，400元。
那么最优解就是500+100+300，即900元，也就是物品1，物品4和物品5，重要度*价格乘积最大，达到3500。

我当时做这道题的时候也是这么想的，但是发现实际中不能这么做，因为有可能会出现以下情况：
剩余钱数：1000
物品1：重要度4，价格1000，乘积4000
物品2：重要度5，价格400，乘积2000
物品3：重要度5，价格500，乘积2500
排序应该是物品1>物品3>物品2
按你的方法是购买物品1
但明显应该购买物品3+物品2利益最大

所以还是老老实实应用单纯形法好了。。。

是这样的，多谢提醒。
那你看这样行不行，算出重要度/价格最高的，然后排序（也就是性价比最高的）。

#11

引用 1 楼 lincolnandlinda 的回复:

这不是典型的线性规划吗, 最常用的算法应该是单纯形法

就是这样！