购物问题算法求解
我现在在商场购物,有N件物品供我选择,价格分别为P1,P2 ... Pn,又商场有一活动,购物满S元,可以获得一份赠品.问:我需要选择购买哪些物品使我能够获得一份赠品并所花的钱最少?
上面这个问题用什么算法求解好呢?算法的时间和空间复杂度是多少.欢迎有兴趣的朋友讨论算法的思路,有源程序最好,谢谢.
[解决办法]
Resolved this question long time ago.You can use "layout " method to resolve it.
[解决办法]
只能把所有可能计算出来，否则你怎么确定哪一种是最优化的？？
===================================================
技术交流不该有界限 资源共享不该有条件
博客空间：http://blog.csdn.net/lovingkiss
资源下载：http://download.csdn.net/user/lovingkiss
Email：loving-kiss＠163.com
本人说明： <我的帖子我做主,结贴率保持１００％>
1、欢迎一切问题有关的交流——无论答案对错；
2、不欢迎 顶、Mark、支持之类口水混分的人；
我保留对非 <散分贴> 蹭分者的厌恶和鄙视...
精通:jīnɡtōnɡ对学问技术等透彻的了解并熟练掌握
所以，我没有精通，只有JZ
===================================================
[解决办法]
仔细想想，似乎遍历也很难。。。。汗~~
这样的题——算法需要相当强悍才行，一般够呛。。。
===================================================
技术交流不该有界限 资源共享不该有条件
博客空间：http://blog.csdn.net/lovingkiss
资源下载：http://download.csdn.net/user/lovingkiss
Email：loving-kiss＠163.com
本人说明： <我的帖子我做主,结贴率保持１００％>
1、欢迎一切问题有关的交流——无论答案对错；
2、不欢迎 顶、Mark、支持之类口水混分的人；
我保留对非 <散分贴> 蹭分者的厌恶和鄙视...
精通:jīnɡtōnɡ对学问技术等透彻的了解并熟练掌握
所以，我没有精通，只有JZ
===================================================
[解决办法]
假设，如果都没有正好等于该优惠价格的，就需要把所有可能都循环列出，然后逐一比较
在这之前还有对价格简单排序。。。。我靠，不用多，10个价格就有无数种可能~~
[解决办法]
这个是比较复杂
每个商品只能买一件嘛!
[解决办法]
mark
[解决办法]
把s看作背包空间，就是装满背包的背包算法
[解决办法]
商品可否重复?
[解决办法]
不可重复购买循环就简单太多了啊。
——不过仔细想想，依旧满复杂的。。。汗~~
===================================================
技术交流不该有界限 资源共享不该有条件
博客空间：http://blog.csdn.net/lovingkiss
资源下载：http://download.csdn.net/user/lovingkiss
Email：loving-kiss＠163.com
本人说明： <我的帖子我做主,结贴率保持１００％>
1、欢迎一切问题有关的交流——无论答案对错；
2、不欢迎 顶、Mark、支持之类口水混分的人；
3、对带有性别的主题和求全部毕业代码者尽量不回答；
我保留对非 <散分贴> 蹭分者的厌恶和鄙视...
精通:jīnɡtōnɡ对学问技术等透彻的了解并熟练掌握
所以，我没有精通，只有JZ
===================================================
[解决办法]
解决办法，先将所有价格P1,P2 ... Pn进行升序排列（假如新列是Q1，Q2....Qm....Qn，n> =m> =1），以排序后最小的价格Pmin开始从左往右累加（可存放在一个参数Para当中），如果累加到Qm时Para> S元时，就可以得到总花费最小的结果集为（Q1+Q2+......Qm）
[解决办法]
要做的主要工作只是排序（楼主你可以自己挑喜欢的排序算法），累加和判断对你来说肯定是小CASE了
[解决办法]
不好意思，回完贴才悟过来，这个问题应该用贪心算法，上面的回复当我没说，是错的
[解决办法]
贪心算法
贪心算法
一、算法思想
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
二、例题分析
1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi <=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。 ?
[解决办法]
算法理论是有了——可是实现起来呢？
我也顺便等答案
===================================================
技术交流不该有界限 资源共享不该有条件
博客空间：http://blog.csdn.net/lovingkiss
资源下载：http://download.csdn.net/user/lovingkiss
Email：loving-kiss＠163.com
本人说明： <我的帖子我做主,结贴率保持１００％>
1、欢迎一切问题有关的交流——无论答案对错；
2、不欢迎 顶、Mark、支持之类口水混分的人；
3、对带有性别的主题和求全部毕业代码者尽量不回答；
我保留对非 <散分贴> 蹭分者的厌恶和鄙视...
精通:jīnɡtōnɡ对学问技术等透彻的了解并熟练掌握
所以，我没有精通，只有JZ
===================================================
[解决办法]
似乎可以参考
http://www.sfcode.cn/soft/00319.htm
找了一下，贪心算法还真啰嗦阿，循环是一个很庞大的东西，一般都找不到最优，只能找到比较好的
===================================================
技术交流不该有界限 资源共享不该有条件
博客空间：http://blog.csdn.net/lovingkiss
资源下载：http://download.csdn.net/user/lovingkiss
Email：loving-kiss＠163.com
本人说明： <我的帖子我做主,结贴率保持１００％>
1、欢迎一切问题有关的交流——无论答案对错；
2、不欢迎 顶、Mark、支持之类口水混分的人；
3、对带有性别的主题和求全部毕业代码者尽量不回答；
我保留对非 <散分贴> 蹭分者的厌恶和鄙视...
精通:jīnɡtōnɡ对学问技术等透彻的了解并熟练掌握
所以，我没有精通，只有JZ
===================================================
[解决办法]
1、先把商品按价格排序（P1 <P2 <P3 <P4... <Px），然后设一个标记位，算sum=P1+P2+...+Pm，直到sum> =S为止；
2、然后从1~m开始，sum=sum-P1-P2...-Pn，直到sum <=S为止；
3、然后从1~n开始，计算sum=sum+P1+P2+...+Pj，直到sum> =S为止；
4、依次循环，直到sum+P1> =S或者sum-P1 <=s停止。
最后整理一下，得出的列表即为获得一份赠品并所花钱最少的商品列表，sum即所花的最少钱。
[解决办法]
楼上的实现不了——完全利用循环比较来实现贪心算法的话，能运行到3000年。。。呵呵
===================================================
技术交流不该有界限 资源共享不该有条件
博客空间：http://blog.csdn.net/lovingkiss
资源下载：http://download.csdn.net/user/lovingkiss
Email：loving-kiss＠163.com
本人说明： <我的帖子我做主,结贴率保持１００％>
1、欢迎一切问题有关的交流——无论答案对错；
2、不欢迎 顶、Mark、支持之类口水混分的人；
3、对带有性别的主题和求全部毕业代码者尽量不回答；
我保留对非 <散分贴> 蹭分者的厌恶和鄙视...
精通:jīnɡtōnɡ对学问技术等透彻的了解并熟练掌握
所以，我没有精通，只有JZ
===================================================
[解决办法]
按照楼主的要求显然是不能用贪心算法的，贪心算法只能得到一个可行解，而楼主要得是最优解。
请注意:
-------------------------------------------
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
--------------------------------------------
[解决办法]
要得到最优解，就要得出所有解。由于楼主限定不能重复拿，显然解空间是有限的。只有用递归得出所有解，然后选出最优解。
[解决办法]
递归，没有那么容易的啦！
===================================================
技术交流不该有界限 资源共享不该有条件
博客空间：http://blog.csdn.net/lovingkiss
资源下载：http://download.csdn.net/user/lovingkiss
Email：loving-kiss＠163.com
本人说明： <我的帖子我做主,结贴率保持１００％>
1、欢迎一切问题有关的交流——无论答案对错；
2、不欢迎 顶、Mark、支持之类口水混分的人；
3、对带有性别的主题和求全部毕业代码者尽量不回答；
我保留对非 <散分贴> 蹭分者的厌恶和鄙视...
精通:jīnɡtōnɡ对学问技术等透彻的了解并熟练掌握
所以，我没有精通，只有JZ
===================================================
[解决办法]
我上面给出的算法绝对可行，注意关键点：x> m> n> ..> 1，而且是整数比较大小，比较的次数最多不超过x+(x-1)+..+2+1=(x+1)*x/2，算法复杂度是O(n^2)。
[解决办法]
我算多了，x表示总共有x件商品，m表示按价格从小到大相加，直到价格超过S时所选中的m件商品，之后再往回从p1~pn的+/-肯定是在这m件商品之内，最坏情况也不过是从m+(m-1)+..+1，算法复杂度和x的关系都不大，最有关系的是m。
[解决办法]
举个例子:
p1=1
p2=2
p3=3
p4=4
p5=5
p6=6
p7=7
p8=8
p9=9
p10=10
现在给定S=31
不信的人可以用我的算法检验一下：
1+2+3+4+5+6+7+8=36> 31
m=8
36-1-2-3-4=26 <31
n=4
26+1+2+3=32> 31
n=3
32-1=31=31
最终选择的列表为：1,4,5,6,7,8
[解决办法]
又是背包问题
[解决办法]
看看我的方法，或许对你有些帮助
http://blog.csdn.net/cfreez/archive/2007/06/27/1668543.aspx
目前只有个思路和例子，还没有统一
[解决办法]
算法不行 mark
[解决办法]
大家都错了
不能重最小的加起,应该重最大的开始加!
例如有8个数字: 3 5 7 8 9 10 14 38 79
"背包 "满为 100
如果从小到大加是 3 + 5 + 7 + 8 + 9 + 10 + 14 + 38 + 79 = 173,只能全部加完才能超过100
如果反过来,从大到小 : 79 + 38 = 117, 只超过了 "17 "!!!!!!
[解决办法]
如果商品可以重复购买就直接重复买被S除余数最小的就可以!!!
(前提是没有一个商品的价格能够被S整除)
[解决办法]
这个问题不难。我实现了以下，我这里规定商品每样只能获取一次。这种情况比较有点点难度，如果商品可以重复取，只要找个能整除的就并且最低价格的商品就行了。
static void Main(string[] args)
{
double[] prices = new double[] { 3, 5, 7, 8, 9, 10, 14, 38, 79 };
double S = 100;
double[] choose = GetChoose(prices, S);
for (int i = 0; i < choose.Length; i++)
Console.Write(choose[i].ToString() + " ");
Console.WriteLine();
}
static double[] GetChoose(double[] prices, double S)
{
List <double> choose = new List <double> ();
bool[] isChoosed = new bool[prices.Length];
for (int i = 0; i < isChoosed.Length; i++)
isChoosed[i] = false;
while (S > 0)
{
double min = double.MaxValue;
int get = -1;
for (int i = 0; i < prices.Length; i++)
{
if (!isChoosed[i])
{
double c = S - prices[i];
if (c < 0) c = -c;
if (min > c)
{
min = c;
get = i;
}
}
}
if (get != -1)
{
choose.Add(prices[get]);
S -= prices[get];
isChoosed[get] = true;
}
}
return choose.ToArray();
}
[解决办法]
"背包 "满为 100
如果从小到大加是 3 + 5 + 7 + 8 + 9 + 10 + 14 + 38 + 79 = 173,只能全部加完才能超过100
排好序后应该从 <100的最大数开始吧..
79+3+5+7+8=102 ,只超过了2....
其实这个跟查找最短路径算法有相似之处,使用不同的路径,得出的结果不同..因为算到这步, 你不会知道下一步算哪个数才是真正达到最小的...不过我觉得上面的算法可以尽量做到最小..
[解决办法]
昏，不管是最小开始+还是从最大开始+，最后得到的“最少钱”结果都一样，而且都要用我提到的步骤：
2、然后从1~m开始，sum=sum-P1-P2...-Pn，直到sum <=S为止；
3、然后从1~n开始，计算sum=sum+P1+P2+...+Pj，直到sum> =S为止；
4、依次循环，直到sum+P1> =S或者sum-P1 <=s停止。
来逐步求精，注意题目要求是：购买哪些物品使我能够获得一份赠品并所花的钱“最少”，如果不进行2，3，4的步骤求精，得出的答案并不一定是最少。这也就是jerryfos(想飞)说自己的算法错了原因，从他的算法再往前多推一步，就是正解。
该算法还可得到一个额外奖励，即最后算出来的列表同时满足花钱“最少”，和购买的商品数量“最多”。反之从最大开始+，按照2，3，4步骤求精后的结果和从最小开始+，最后得出的结果是一样的。但是从最大开始加，你还要先多判断一次，看看最大项是否大于S。
[解决办法]
从最小开始+，只要判断一次，如果第一个最小项> S，那么后面的全都不用做，结果即为P1。
BTW：算法该不该优化不是看某几个具体例子来分析从什么地方+最优，而是取所有随机情况下的最好和最坏情况的平均值。比如，第一最小项P1> S，那么从最后Px开始+，算法复杂读是N，而从P1开始+，算法复杂度是1，那么是不是说从最小开始+就强过从最大开始+？还对这个问题没有明确答案的，推荐你回去温习数据结构和算法的教科书。
[解决办法]
up
