algorithm - 公平产品分配算法

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] 因为第一天有 4 个产品，第三天有 2 个产品(差异 > 1)

分配无效: [abc,aabc,aab] 因为第一天有一个产品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() —— 它们只是按照您的预期进行。)