Kattis背包C ++ [关闭]

Question

关闭。这个问题需要details or clarity。它当前不接受答案。

---

是否要改善此问题？通过editing this post添加详细信息并澄清问题。

[<13天前关闭。

目前，我正在寻求Kattis的一生，以使这个问题在C ++中起作用。我认为这似乎是一个背包问题，我已经阅读了一些有关此问题的主题，但我真的不知道该如何解决！任何提示或指示将非常适用！我将在此处发布从kattis复制的问题描述！谢谢！

说明：

Kattis正在几次远足旅行中带走她的一只小猫，他们需要收拾行囊。它们有许多物品（帐篷，烹饪设备，食物，衣服等），需要在它们之间尽可能均匀地分配重量。万一重量不能平均分配，Kattis将承担额外的重量。您可以帮助他们为每次旅行在他们之间拆分项目吗？

输入输入最多包含150个远足旅行。每个行程在输入中以一行形式给出。该行以1≤n≤20（它们需要拆分的项目数）开头。然后跟随每个项目的重量。重量均在[100,600]克的范围内。输入结束由包含单个0的行指示。

输出对于每次旅行，请输出两个背包的重量。首先输出Kattis背包的重量。

Answer 1

这个问题可以通过背包解决。让我们定义一个dp函数F(pos, sum)和一个数组dp[pos][sum]，它告诉我们是否以sum = pos到达位置sum。

我们使用以下dp转换：

F(pos + 1, sum + weights[pos]) //取当前体重

F(pos + 1, sum) //跳过当前的重量

基本情况：if (pos == n + 1)

更新我们的答案

：让我们保留一个全局变量diff，该变量跟踪两个背包的重量之间的绝对差。另一个变量total是所有权重的总和。我们可以在基本案例中找出两个背包的重量，分别是sum和total - sum。利用此信息，我们可以更新diff并存储两个背包的重量。

void F(int pos, int sum) {
     if (pos == n + 1) {
         int first = sum, second = total - sum;
         if (abs(first - second) < diff) {
              diff = abs(first - second);
              first_backpack = first, second_backpack = second;
         }
         return;
     }
     if (dp[pos][sum]) return;
     dp[pos][sum] = 1;

     F(pos + 1, sum);
     F(pos + 1, sum + weights[pos]);
     return;
}

复杂度

：O（n *和），其中n = 20，和= 20 * 600