李晓明

人们常常讲，要合理分配时间，合理分配资金等。抽象来看，说的都是要将某种掌握的资源，分配投入到某些事项上，希望得到最好的综合回报。这类追求很有意义，因而得到人们的广泛研究。同时这种事情也很复杂，到目前为止并没有一个普适的方案。其复杂性体现在几个方面：第一，每一个可投入的事项（如股票）能得到多少回报，常常并不是事先能够明确的;第二，回报不一定就是金钱，而其他方面（如愉快）常常很难量化，因而难以评估;第三，情势是动态变化的，还有机会成本的问题，今天决定投入（如时间）某事项了，就意味着明天可能难以改投更有意义的事项。

我们这里讨论一种相对单纯（但并不一定简单）的情境，看算法能怎么发挥作用。

考虑一定量的资金n，要分配投入到m个不同的项目上，以获得最大的回报。假设在每个项目上的投入和回报的对应关系是预先知道的（如银行定期存款的利息）。下面是一个具体的例子，假设你有n=5万元钱，可以安排在m=3个项目上，表1给出不同的投资量分别可产生的回报。

你面对的问题就是，如何将5万元钱分配到这3个项目上，让总的回报最大。例如，若你把5万元都投在项目1上，得到回报9，而你在项目1上投4万，项目3上投1万，得到回报7+3=10，就要好一些。是不是还有更好的呢？一般的问题就是，给定任意一个这样的投资回报表，能否有一个系统化的方法（算法），求出最大回报，以及对应最大回报的“投资组合”。

我们将从问题定义、求解思路、算法描述、算例分析和算法性质这五个方面展开对这个问题的讨论。……