购物问题算法求解

我现在在商场购物,有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
　　 求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；