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 team
56 9.0 1 t1
54 9.1 2 t1
35 8.0 2 t2
32 8.0 3 t1
20 8.5 1 t2
18 9.0 3 t2
16 9.1 2 t2
15 8.0 3 t2
13 7.0 3 t1
10 8.5 4 t2
7 9.0 4 t2
5 8.0 2 t1
4 7.0 3 t1
3 8.5 4 t1
2 9.0 3 t1
1 8.5 4 t2
0 9.0 3 t2
0 8.5 4 t1
0 9.0 3 t2
0 8.5 4 t1
0 9.0 3 t1
0 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。

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

补充：
用回溯算法实现了下，代码放在github，用几个测试用例简单的测试了下，都是正确的，效率不是很高，你自己优化一下，下面是我的输出：

输入数据:
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}

如果正确，望采纳