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最大的记录。在选取过程中需要注意一些条件：一条记录只能被选择一次相同的Team选择的次数小于等于7每个position的限制选举的条数达到11，或credits达到100，则停止如果credits先达到100，则考虑一种置换策略。补充：貌似贪心好像不行，换种思路，用回溯的方法去考虑：首先，对所有记录按照points倒序排序，构建一个搜索空间树，树高为11。所以原问题就变成了搜索树的最佳路径的问题。每次选取points最大的记录，向下搜索时，可以根据条件过滤掉没有必要的分支。每一步搜索时必须满足一下条件：相同记录不能被搜索两次。相同的Team选择的次数小于等于7。每个position的限制。对已选取的记录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}