有180个球。
有 70 个桶。
每个球的价值取决于它所在的桶：
ball1 = { 1, 14, 2, 3, 4 ... } //70 values in total for each bucket
ball2 = { 24, 2, 23, 2, 5 ... }
...
每个桶有一个它可以承载的最大球数，但是 70 个桶可以承载的球总数是 180，即所有 180 个球都可以完全装下。（每个桶必须至少携带 1 个球）
{bucket1, 3} {bucket2, 1} { bucket3, 2} {bucket4, 1} ...
你如何最大限度地提高球的位置？
我试图暴力破解，在数了排列的数量后很快就后悔了。
这似乎是一个二分图最大权重匹配问题。棘手的部分是如何构造二分图，以便我们可以应用多项式时间算法来解决问题。
为了使问题更简单，假设我们有 3 个球和 2 个桶：
Ball 1: {1, 10},
Ball 2: {9, 20},
Ball 3: {7, 9};
Bucket 1: 2
Bucket 2: 1
我想构建如下图：
主要思想是构造一个二元图，使得节点的左边部分代表球，而另一部分是桶的节点。我们给每个桶的容量一样多的节点，现在我们可以应用最大权重匹配算法来解决我们的问题。
由于复杂性，这是一种最好通过“我可以在固定时间内达到什么最佳结果”方法来解决的问题。如果您需要真正的全局最大值，那么这对您不起作用。
我的第一种方法是模拟退火：
1) 随机放置球（取决于您在每个桶中至少有一个球的限制）
2）计算目标函数（你必须已经从你的蛮力方法中得到这个）
3) 考虑随机交换两个球、将一个球移入另一个桶（如果约束允许）等操作。
4）重新计算目标函数
5）如果目标函数更好，请始终接受更改，而且（这很重要），如果目标函数更差且概率衰减 exp(-constant * time)，也接受更改。（这称为温度函数）。
6) 再转一圈。
这种方法将允许好的桶粘在一起，并在早期阶段允许状态从局部最大值反弹。这里的科学是为“常数”找出一个好的值。