算法问题：若干数中取出n个数，之和最接近某个数

Question

算法实例－关于旅行者的背包问题
基本问题： 
0/1背包问题中，需要对容量为C的背包进行装载。从N个物品中选取装入背包的物品，每件物品I的重复为W(I)，价值为P(I)。如何装入价值最大的物品？
算法：
贪心准则1－从剩余的物品中找出一个可以装入背包的价值最大的物品。
贪心准则2－从剩余的物品中找出可以装入背包的重量最小的物品。
贪心准则3－计算价值密度P(I)/W(I)。从剩余的物品中选择可装入包的P/W(I) 物品。
贪心算法之K阶优化－从答案中取出K件物品，并放入另外K件，获得的结果不会比原来的差。这样优化整个放入物品的序列。
动态规划－用递归进行计算求解。每一步求出基于现在状况下的最优解。（特点－计算复杂）
回溯算法－首先形成一个递归算法，去找到可获得的最大收益。即列出所有的候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找出所需要的解。（特点－候选解数量庞大）
变形问题：
·货郎的背包
·野外生存者的背包
·公司经理（？）的背包。

Answer 1

哦，这个是的0-1规划问题，我手里有资料，Delphi运筹学的。
我这个问题比你这个还麻烦一些。
http://community.csdn.net/Expert/topic/4872/4872394.xml?temp=.7980463

Answer 2

你的问题缺了几个隐含的条件，我来重新阐述这个问题，并给出在几种不同隐含条件下的解决方法
1）你需要的是在有限空间里装入尽量多的文件
2）你需要在有限空间中装入价值量最大的尽量多的文件第一种情况的最优解很简单
解决方法很简单，把文件按照文件大小排序，然后从最小的开始往光盘上刻，这样可以保证在光盘里包含尽量多的文件第二种情况，解决方法不少，我给出我的
你的每个文件首先必须有他的价值属性（p），可能是星级或者别的什么，设文件大小为（s），则单位大小的价值（单价）为dp=p/s,你把文件按照dp由大到小排序，dp相同的文件，再根据s由小大排序，形成的序列就是你添加文件的顺序，如果添加某个文件后总大小超过大小限制则选择下一个单价下的第一个文件（下一个单价的最小文件）

Answer 3

枚举法：（因为我前几天刚写过一个组合的算法，稍微改动一下，就适合你这个了）http://community.csdn.net/Expert/topic/5305/5305770.xml?temp=.9931299<SCRIPT LANGUAGE="vbScript">
'所有文件大小的数组。
Arr=array(200,300,350,80,20)''创建全局字典对象，用来存储所有得到的原子结果
Set dict=CreateObject("Scripting.Dictionary")Dim  a(100)
strLength=ubound(Arr)+1
 
 Dim  best,spare,mass,aim
spare=700
aim=700For x=1 To strLength
 a(0)=x 
 ''计算5选1，5选2，5选5组合
 combine strLength,x 
next
 
sub combine(m,  k) 
''计算组合在m里面选k个元素的全部组合情况，添加到字典对象里
 i=0
 j=0 
 For i=m To k Step -1
  a(k)=i 
  if (k>1)  then
   combine i-1,k-1  
  else 
   tempStr=""
   mass=0  
   for  j=1 To a(0)  
    tempStr=tempStr & a(j) 
    mass=mass+Arr(a(j)-1)
   Next 
   if (aim-mass)<spare and mass<aim then
spare=aim-mass
 best = tempStr
   end if
   ''加到字典里   
dict.add tempStr,mass
  End if 
 next 
End sub Main()Sub Main
 ''输出显示结果
 For i=0 To dict.count-1
  Document.write  dict.keys()(i) & ":" &  dict.items()(i)  & "<br/>"
 next
End sub
  Document.write "最优方案：" & best & ":" &  dict.item(best)   & "<br/>"
</SCRIPT> 
5:20
4:80
3:350
2:300
1:200
45:100
35:370
25:320
15:220
34:430
24:380
14:280
23:650
13:550
12:500
345:450
245:400
145:300
235:670
135:570
125:520
234:730
134:630
124:580
123:850
2345:750
1345:650
1245:600
1235:870
1234:930
12345:950
最优方案：235:670
就是选择第2个3个和5个文件。

Answer 4

to:
danjiewu(阿丹)利用运筹学可以不必穷举。我上面的算法是穷举。如果有兴趣和时间可以搞一搞线性规划，就是需要查书找运筹学资料。
而且目前计算机速度解决这个问题，穷举不会感觉速度太慢，就无所谓了。

Answer 5

上面例子存成HTML就可以运行。

Answer 6

yizhu2000()的方法不适合解决这个问题吧？按照我的理解，楼主的意思应该是，当前有若干不同大小的物品，怎样组合才能获得最大的背包空间利用率。而不是装入最多的物品或者最大价值的物品。我感觉要获得最大的空间利用率比你说的两个问题要难。

Answer 7

如果不要求刚好n个文件，代码少一些
如果刚好n个文件，可以剪枝掉很多
例如，所有文件大小为a0,a1,a2,……,aM，都<=目标容量V
已经按照从小到大排序
之后就是DP了
先放a0
再对于0和a0分别放/不放a1，得到0,a0,a1,a0+a1四个解
再对于上面四个解分别放/不放a2，得到0,a0,a1,a2,a0+a1,a0+a2,a1+a2,a0+a1+a2八个解
……
也就是穷举所有的放/不放的组合
由于总容量V，复杂度为O(V*M)
如果限制了文件数n，当前已经考察了K个文件，对于某个包含k个文件的解s，连续取aK、aK+1、……直到取满n个文件（从文件K到文件K+（n-k-1）的容量和可以事先用O(n^2)得到），再看是否超出了V就可以了，超出的直接放弃

Answer 8

用一个递归调用吧。就不要考虑什么了。
这样做确实有些操作是多余的。效率不好，空间占用也比较高。
下面是C#的语法。
====================================================using System;namespace Arith
{
    /// <summary>
    /// Class1 的摘要说明。
    /// </summary>
    class Class1
    {        static UInt32 nLimit = 0;
        static String result = String.Empty;        /// <summary>
        /// 应用程序的主入口点。
        /// </summary>
        [STAThread]
        static void Main(string[] args)
        {
            String slist = string.Empty;
            System.Text.RegularExpressions.Regex rexp = new System.Text.RegularExpressions.Regex(@"^(?:\d{1,4}[, -])+\d:\d{1,5}$");            do
            {
                Console.WriteLine("请输入(格式如:11,12,13,15,...,8,9:88):");
                slist = Console.ReadLine();
            }
            while (!rexp.IsMatch(slist));            UInt32 nMax =  UInt32.Parse(slist.Split(":".ToCharArray())[1]);
            nLimit = nMax;            String[] asList = slist.Split(":".ToCharArray())[0].Split(", -".ToCharArray());
            System.Collections.ArrayList aList = new System.Collections.ArrayList(asList.Length);            for (int i = 0; i < asList.Length; i++)
            {
                aList.Add(UInt32.Parse(asList[i]));
            }
            Console.WriteLine(nMax);            for (int i = 0; i < aList.Count; i++)
            {
                GetLimit((UInt32)aList[i],nMax,aList.Clone() as System.Collections.ArrayList);
            }            Console.WriteLine("======================================");
            Console.WriteLine(result);
            Console.WriteLine("敲回车结束....");
            Console.ReadLine();
        }        static void GetLimit(UInt32 baseVal, UInt32 maxVal, System.Collections.ArrayList alist)
        {
            UInt32 newMaxVal = maxVal-baseVal;
            alist.Remove(baseVal);            foreach (UInt32 al in alist)
            {
                if (newMaxVal==0)
                {
                    nLimit = newMaxVal;
                //      result = String.Format("{0}\n{1}",result,GetString(alist));
                }
                if (nLimit == 0)
                {
                    // ok.
                    return;
                }
                if (newMaxVal < nLimit)
                {
                    nLimit = newMaxVal;
                    result = String.Format("{0}",GetString(alist));
                }
                if (newMaxVal < al)
                {
                    // next
                    continue;
                }                GetLimit(al, newMaxVal, alist.Clone() as System.Collections.ArrayList);            }            // alist为空的时候就被落下来了。写的不好。
            if (newMaxVal < nLimit)
            {
                nLimit = newMaxVal;
                result = String.Format("{0}",GetString(alist));
            }        }        static string GetString(System.Collections.ArrayList alist)
        {
            System.Text.StringBuilder sb = new System.Text.StringBuilder();
            alist.TrimToSize();            foreach(UInt32 al in alist)
            {
                sb.AppendFormat("{0} ",al);
            }            return sb.ToString();
        }
    }
}

Answer 9

呓，类似的已经有啦。不过稍有区别。(@"^(?:\d{1,4}[, -])+\d:\d{1,5}$");
--------------------------
gai:
(@"^(?:\d{1,4}[, -])+\d{1,4}:\d{1,5}$");

Answer 10

1.NP问题，k阶优化
2.最近看了一下遗传算法，介绍说遗传算法很适合这类经典的最优解问题
3.如果规模小就遍历