java-多维度求最优解

Question

拿出11条数据//条件每个位置(position)的人数限制每队(team)人数不能超过7人credits的总和在100分之内（包含100）总分(points)最高//位置人数限制position-1 : 1 position-2 : 3-5 position-3 : 1-3 position-4 : 3-5//模拟数据{points credits position team56 9.0 1 t154 9.1 2 t135 8.0 2 t232 8.0 3 t120 8.5 1 t218 9.0 3 t216 9.1 2 t215 8.0 3 t213 7.0 3 t110 8.5 4 t27 9.0 4 t25 8.0 2 t14 7.0 3 t13 8.5 4 t12 9.0 3 t11 8.5 4 t20 9.0 3 t20 8.5 4 t10 9.0 3 t20 8.5 4 t10 9.0 3 t10 8.5 4 t2... ... ... ...}

Answer 1

这个和背包问题有点类似啊，首先包容量是 100，即credits <= 100。其次拿到的所有数据的Sum(points)最大。光这两点就和背包问题非常相似。

背包问题是这样描述的：
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

背包问题求解使用了贪心算法，其中贪心策略是：每次选取单位重量价值最大的物品。

你这里类比一下，贪心策略是：每次选取单位credits points最大的记录，即points / credits最大的记录。
在选取过程中需要注意一些条件：

1. 一条记录只能被选择一次

2. 相同的Team选择的次数小于等于7

3. 每个position的限制

4. 选举的条数达到11，或credits达到100，则停止

5. 如果credits先达到100，则考虑一种置换策略。

补充：
貌似贪心好像不行，换种思路，用回溯的方法去考虑：

首先，对所有记录按照points倒序排序，构建一个搜索空间树，树高为11。所以原问题就变成了搜索树的最佳路径的问题。每次选取points最大的记录，向下搜索时，可以根据条件过滤掉没有必要的分支。每一步搜索时必须满足一下条件：

1. 相同记录不能被搜索两次。

2. 相同的Team选择的次数小于等于7。

3. 每个position的限制。

4. 对已选取的记录Sum(points) <= 100。

一旦搜索路径上不满足上述条件，则回溯，到另一个分支继续搜索。所以整个是一个递归的过程。

补充：
用几个测试用例简单的测试了下，都是正确的，效率不是很高，你自己优化一下，下面是我的输出：

输入数据:
1   56  9.0  1   1  2   54  9.1  2   1  3   35  8.0  2   2  4   32  8.0  3   1  5   20  8.5  1   2  6   18  9.0  3   2  7   16  9.1  2   2  8   15  8.0  3   2  9   13  7.0  3   1  10  10  8.5  4   2  11  7   9.0  4   2  12  5   8.0  2   1  13  4   7.0  3   1  14  3   8.5  4   1  15  2   9.0  3   1  16  1   8.5  4   2  17  0   9.0  3   2  18  0   8.5  4   1  19  0   9.0  3   2  20  0   8.5  4   1  21  0   9.0  3   1  22  0   8.5  4   2  选取的数据：
1   56  9.0  1   1  2   54  9.1  2   1  3   35  8.0  2   2  4   32  8.0  3   1  6   18  9.0  3   2  7   16  9.1  2   2  8   15  8.0  3   2  10  10  8.5  4   2  11  7   9.0  4   2  12  5   8.0  2   1  14  3   8.5  4   1  sumPoints:251, sumCredits:94.20,
 position-1 picked(1): 1 , position-2 picked(3-5): 4 , position-3 picked(1-3): 3 , position-4 picked(3-5): 3  
 team picked(less than 7):{1=5, 2=6}