公平的产品分销算法

Question

这是我的问题:

• 有n家公司分销产品.
• 所有产品应在k天内分发
• 公司Ci的分销产品应该是连续的 - 这意味着它可以在2,3,4,5天分发,但不能分发2,3,6,7
• 公司Ci在第j天的分发产品数量应该在第j-1天小于(或相等)(如果在第j-1天有任何数据)
• 第i天和第j天之间的分布式产品之间的差异不应大于1

例:

我们有3天的时间来分发产品.A公司的产品:a,a,a,a,a.B公司产品:b,b,b.C公司产品:c,c

公平分配: [aab,aabc,abc]

分配无效: [aabc,aabc,ab]因为第1天有4个产品,第3天有2个产品(差异> 1)

分配无效: [abc,aabc,aab]因为第1天有一个产品A,第二天有2个产品A,所以产品A的分配不是不减少

编辑, 如果有一个案例,使公平分配不可能请提供简短说明,我会接受答案

Answer 1

Gareth Rees 对 djna 答案的评论是正确的——以下反例是无法解决的：

• 3天，A公司7件，B公司5件

我使用以下最愚蠢的暴力 Perl 程序对此进行了测试（尽管效率非常低，但只需要不到一秒的时间）：

my ($na, $nb) = (7, 5);
for (my $a1 = 0; $a1 <= $na; ++$a1) {
    for (my $a2 = 0; $a2 <= $na - $a1; ++$a2) {
        my $a3 = $na - $a1 - $a2;
        for (my $b1 = 0; $b1 <= $nb; ++$b1) {
            for (my $b2 = 0; $b2 <= $nb - $b1; ++$b2) {
                my $b3 = $nb - $b1 - $b2;
                if ($a1 >= $a2 && $a2 >= $a3 || $a1 == 0 && $a2 >= $a3 || $a1 == 0 && $a2 == 0) {
                    if ($b1 >= $b2 && $b2 >= $b3 || $b1 == 0 && $b2 >= $b3 || $b1 == 0 && $b2 == 0) {
                        if (max($a1 + $b1, $a2 + $b2, $a3 + $b3) - min($a1 + $b1, $a2 + $b2, $a3 + $b3) <= 1) {
                            print "Success! ($a1,$a2,$a3), ($b1,$b2,$b3)\n";
                        }
                    }
                }
            }
        }
    }
}

请看一下并确认我没有犯任何愚蠢的错误。max()（为了简洁起见，我省略了它们min()——它们只是做你所期望的事情。）