我想将k
球分配到不同容量的n
箱中。在给定n
,k
和bin容量的情况下,如何对分布进行排名和取消排名?
例:n := 3
k := 4
bin capacities := 3,2,1
垃圾箱中的球:1,2,1
,2,1,1
,2,2,0
,3,0,1
,3,1,0
:= 5
有公式吗?
最佳答案
我不知道这种技术是否有标准名称,但这是我通过动态编程成功地解决了许多问题的一种方法。
我使用动态编程来构建可以发生排名/不排名的数据结构,然后构建逻辑来执行排名/不排名的事情。
动态编程是最难的。
import collections
BallSolutions = collections.namedtuple('BallSolutions', 'bin count balls next_bin_solutions next_balls_solutions');
def find_ball_solutions (balls, bin_capacities):
# How many balls can fit in the remaining bins?
capacity_sum = [0 for _ in bin_capacities]
capacity_sum[-1] = bin_capacities[-1]
for i in range(len(bin_capacities) - 2, -1, -1):
capacity_sum[i] = capacity_sum[i+1] + bin_capacities[i]
cache = {}
def _search (bin_index, remaining_balls):
if len(bin_capacities) <= bin_index:
return None
elif capacity_sum[bin_index] < remaining_balls:
return None
elif (bin_index, remaining_balls) not in cache:
if bin_index + 1 == len(bin_capacities):
cache[(bin_index, remaining_balls)] = BallSolutions(
bin=bin_index, count=1, balls=remaining_balls, next_bin_solutions=None, next_balls_solutions=None)
else:
this_solution = None
for this_balls in range(min([remaining_balls, bin_capacities[bin_index]]), -1, -1):
next_bin_solutions = _search(bin_index+1, remaining_balls - this_balls)
if next_bin_solutions is None:
break # We already found the fewest balls that can go in this bin.
else:
this_count = next_bin_solutions.count
if this_solution is not None:
this_count = this_count + this_solution.count
next_solution = BallSolutions(
bin=bin_index, count=this_count,
balls=this_balls, next_bin_solutions=next_bin_solutions,
next_balls_solutions=this_solution)
this_solution = next_solution
cache[(bin_index, remaining_balls)] = this_solution
return cache[(bin_index, remaining_balls)]
return _search(0, balls)
这是产生排名解决方案的代码:
def find_ranked_solution (solutions, n):
if solutions is None:
return None
elif n < 0:
return None
elif solutions.next_bin_solutions is None:
if n == 0:
return [solutions.balls]
else:
return None
elif n < solutions.next_bin_solutions.count:
return [solutions.balls] + find_ranked_solution(solutions.next_bin_solutions, n)
else:
return find_ranked_solution(solutions.next_balls_solutions, n - solutions.next_bin_solutions.count)
这是产生解决方案等级的代码。请注意,如果提供的答案无效,它将爆炸。
def find_solution_rank (solutions, solution):
n = 0
while solutions.balls < solution[0]:
n = n + solutions.next_bin_solutions.count
solutions = solutions.next_balls_solutions
if 1 < len(solution):
n = n + find_solution_rank(solutions.next_bin_solutions, solution[1:])
return n
这是一些测试代码:
s = find_ball_solutions(4, [3, 2, 1])
for i in range(6):
r = find_ranked_solution(s, i)
print((i, r, find_solution_rank(s, r)))