用0-1背包问题解决一些奇奇怪怪的需求

发表于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 6 分钟

前言

在工作中遇到了一个相当奇怪的要求。一开始，每个人自由组队完成任务，有些人超额完成，有些人未能完成，因此分数有多有少。为了能够尽可能多地减少工作量，需要重新分配队伍，实际上就是相互挂名，最后结算的时候抬过分数线。而有一个更奇怪的要求，就是组里面挂了名字之后，分数会被新来的平均分摊，多的人会变少，少的人会变多。

这下强度一下就上来了。

思考

整个过程很乱，但也没关系。我们一步步拆解。

拆解

既然难以思考，那就干脆拆成两个部分，分别是带约束减分（超额人员挂名）和带目标加分（未达标人员均摊）。

带约束减分这个过程也就可以看成一个0-1背包问题。

背包问题：

我现在有这么大的背包，然后有这么多东西，只能选择放入与不放入，那么能放多少。

现在这个问题：

现在部门有这么多的未达标人员，然后有这么多分数，只能选择挂名或不挂名，那么能挂多少。

简直太像了不是吗？

基本思路建模

既然这样，那我们就来试试建立一个数学模型。

对于人员 ，达标线为 ，超额完成后分数为 ；如果本来只有他一个人，组内成员总数为 ，那么一个组可以获得的分数就全为个人所得；如果增加一个组员 ，则组内成员总数变为，那么 的分数变为：

同时，对于 ，本来只有 ，但是挂名后，分数变为：

这似乎很好理解。

但是， 能挂多少呢？已知挂 人将损失 ，挂 人将损失 ，挂 人将损失 ，依此类推。

领导为了实现工作量最小化，也就希望超额完成人员尽可能榨干所有的分数。因此，损失的最大值就是超额值，即对于 来说，。经过挂名后， 将尽可能接近 。

搜索建模

既然我们明确了基本的思路，接下来就是搜索过程了。我们应该选择什么样的策略呢？

如果想简单化一点，我们不如这么想，如果粒度足够小，那么这个分数一定将更为接近超额值。

观察挂人后的损失值：

那么最小粒度就是 。意思就是， 的单人小组全部只加 人，就能够达到 的最小化。

听起来没问题。

但是呢，我们仔细想想，到底是多个 接近 ，还是上述几个组合起来接近 呢？

这可不好说。

让我们不选择 的另一个理由，实际上也是希望带更多的人，用更细碎的分值把未达标人员送过线，而不是仅在单人组带一个，容易浪费分数。

因此，搜索的过程就决定是深度搜索了。

也就是说，我们将按照如下图所示的结构进行搜索：

graph TB
A((搜索))
B((1人))
C((2人))
D((3人))
E((4人))
F((5人))
A-->B
A-->C
A-->D
A-->E
A-->F
G((1人))
H((2人))
I((3人))
J((4人))
K((5人))
B-->G
B-->H
B-->I
B-->J
B-->K

从根节点开始，每次计算挂名后还剩多少分，超出分数限制则剪枝回溯。

就假设搜索过程就如上图，只有 层，我们可以根据叶子节点整理出这些个结果：

1
2
3
4
5
6
7
8
9
1人, 1人
1人, 2人
1人, 3人
1人, 4人
1人, 5人
2人
3人
4人
5人

翻译一下，这个结果从上往下说的就是：

1
2
3
4
5
6
7
8
9
2个单人队伍挂1人
1个单人队伍挂1人、1个单人队伍挂2人
1个单人队伍挂1人、1个单人队伍挂3人
1个单人队伍挂1人、1个单人队伍挂4人
1个单人队伍挂1人、1个单人队伍挂5人
1个单人队伍挂2人
1个单人队伍挂3人
1个单人队伍挂4人
1个单人队伍挂5人

这就是搜索的结果。

那么，怎么知道搜索到最优解呢？

就是计算出每个结果的扣分最大值，直到找到一个最大的值，就认为这个是最优解。

实现

既然有了这个想法，那我们就来实现吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def find_best(target, coins):
  best_choice = [0] * len(coins)
  best_total = 0
  
  def dfs(index, current_choice, remaining):
    nonlocal best_choice, best_total
    # 如果剩余值小于0，停止搜索
    if remaining < 0:
        return
    # 如果当前组合更接近目标值，更新最佳选择
    current_total = target - remaining
    if current_total > best_total and current_total <= target:
      best_total = current_total
      best_choice = current_choice[:]
    # 如果已经检查到最后一个，停止递归
    if index >= len(coins):
      return
    # 尝试不同的选择
    max_count = int(remaining // coins[index])
    for count in range(max_count, -1, -1):
      current_choice[index] = count
      dfs(index + 1, current_choice, remaining - count * coins[index])
  
  # 开始深度优先搜索
  dfs(0, [0] * len(coins), target)
  return best_choice

其中，nonlocal表示dfs方法中的best_choice与best_total并非本地变量，而是来自外部函数的变量，进而修改外部函数find_best中的best_choice与best_total。

于是，为了完整性，加上其他的内容，形成主函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
MAX_MEMBER = 9          # 最大组员数
GROUP_SCORE = 0.5       # 单组固定分数
TARGET_VALUE = 1.075    # 给定的目标值
# 从单人组挂名为多人组时，原单人组组员损失的分数列表
coins = [
  GROUP_SCORE * (1 - 1 / i) for i in range(2, MAX_V)
]
# 最终选择，索引从小到大代表多人组总人数的从小到大
# 即：2人、3人、4人...
choice = [0] * len(coins)
# 示例使用
choice = find_best(TARGET_VALUE, coins)
print("Coins:", coins)
print("Choice:", choice)

# 输出最优解使得原单人组组员扣分分值
total = sum(choice[i] * coins[i] for i in range(len(coins)))
print("Total value of coins used:", total)

最终也就能够输出：

1
2
3
Coins: [0.25, 0.33333333333333337, 0.375, 0.4, 0.4166666666666667, 0.4285714285714286, 0.4375]
Choice: [0, 2, 0, 1, 0, 0, 0]
Total value of coins used: 1.0666666666666669

可以看到，最优解就是选择 个单人组，每组挂 人；再选择一个单人组，挂 人，这样原单人组组员将从超额 分，降到 。

确实已经被榨干了。

这也就是 的最大挂人方案。