算法的数字公平分配为两组 [英] Algorithm for fair distribution of numbers into two sets
问题描述
给定一组n个数字（1＆其中; =正＆其中; = 100），其中每个数为1和450之间的整数，我们需要分发的那些组数字为两组A和B，以使得以下2箱子持有正确的：
Given a set of n numbers (1 <= n <= 100) where each number is an integer between 1 and 450,we need to distribute those set of numbers into two sets A and B, such that the following two cases hold true:
- 在总人数中的每一组相差最多为1。
- 在A的所有数字之和是为几乎等于尽可能所有的数字B中的总和，即分配应该是公平的。
有人能提出一个高效的算法为解决上述问题呢？
Can someone please suggest an efficient algorithm for solving the above problem ?
感谢你。
推荐答案
由于人数不多是不是NP完全问题。
Since the numbers are small it is not NP-complete.
要解决这个问题，你可以使用动态规划：
To solve it you can use dynamic programming:
请一个三维布尔值表 其中，真正在T [S，N，I]指和S可以用以下指数n个元素我的一个子集来达到。 来计算t的值[S，N，i]于检查吨〔S，N，I-1]和T [秒 - A [1]中，n-1，I-1]。 然后看通过表中第二个索引n / 2，找到最佳的解决方案。
Make a three-dimensional table of booleans where true at t[s, n, i] means that the sum s can be reached with a subset of n elements below index i. To compute the value for t[s, n, i] check t[s, n, i-1] and t[s - a[i], n-1, i-1]. Then look through the table at second index n/2 to find the best solution.
编辑：：您其实并不需要一次完整的表。你可以做一个二维表t_i [S，N]为每个索引i和计算表我从表I-1，所以你只需要其中的两个二维表，从而节省了大量的内存。 （感谢马丁福。）
You actually don't need the complete table at once. You can make a two dimensional table t_i[s, n] for each index i and compute the table for i from the table for i-1, so you only need two of these two-dimensional tables, which saves a lot of memory. (Thanks to Martin Hock.)
这篇关于算法的数字公平分配为两组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
