背包变形算法

Question

作为一项作业，我需要用Java编写以下程序：

在书架上有一叠N本书需要由K个作者手动复制。每本书都有Ui页，其中Ai是该书的编号。

我们需要给每位作者连续的书籍，并且不能拆分一本书的页面。

编写一个程序，将书籍分配给作者，并最小化每位作者复制的最大页数。

用户将输入一个数字字符串作为输入，其中第一个数字是书籍数量N，第二个数字是作者数量K，其余数字是每本书的页数。

程序将输出每位作者复制的最大页数。

例如：

输入：15 6 30 40 10 40 50 20 30 40 10 70 10 50 30 50 10 输出：90

在这个例子中，第一个作者可以取书1 = 30和书2 = 40，但不能取例如书1 = 30和书3 = 10。换句话说，你只能从书堆的顶部选书而不混淆它们。

以下是我的实现：

import java.util.*;

public class Library {

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);

    // to work with 1.6 erase the second "Integer"
    //in 1.7 this works properly
    List<Integer> booksList = new LinkedList<Integer>();
    System.out.printf("Give: ");

    String answer = input.nextLine();
    String[] arr = answer.split(" ");

    for (String num : arr) {
        booksList.add(Integer.parseInt(num));
    }

    int books = booksList.remove(0);
    int writers = booksList.remove(0);

    while (booksList.size() > writers) {
        mergeMinimalPair(booksList);
    }

    System.out.println(getMax(booksList));
}

public static void mergeMinimalPair(List<Integer> books) {
    int index = 0;
    int minValue = books.get(0) + books.get(1);
    for (int i = 1; i < books.size() - 1; i++) {
        if ((books.get(i) + books.get(i + 1)) < minValue) {
            index = i;
            minValue = books.get(i) + books.get(i + 1);
        }
    }
    combine(books, index, index + 1);
}

public static void combine(List<Integer> books, int indexA, int indexB) {
    Integer a = books.get(indexA);
    Integer b = books.get(indexB);
    books.remove(indexB); 
    books.add(indexA, a + b);
    books.remove(indexB);
}

public static int getMax(List<Integer> books) {
    int max = books.get(0);
    for (int i = 1; i < books.size(); i++) {
        if (books.get(i) > max) {
            max = books.get(i);
        }
    }
    return max;
}
}

我每次将书籍的最小配对合并，直到列表的长度等于作家数量为止，但这种方法不起作用，在这个例子中输出的是100而不是90。

我听说过动态规划解决背包问题的方案和暴力解决方案，但在我的大学里他们还没有教我们动态规划，所以无论是教授混淆了我们知道的内容还是他想让我们找到一个暴力解决方案。

我确信我的解决方案能够起作用，但出于某些原因它就是不起作用，如果您能指点我其他解决方案的提示，无论是在这个问题上还是在哪里我会很高兴。

您可以向我指出DP解决方案或者暴力解决方案，但是请注意，如果您指向DP解决方案，我几乎对DP实施一无所知。

编辑:我已经看过一些类似于背包问题的问题，但我找不到一个带有这个变化的问题和一个我能理解的非DP解决方案。

- Jason Kur

---

你有没有看过与你问题相关的其他问题？我可以看到一堆暴力解决方案;-) - g13n

输入是否完整？ - Paul Vargas

我知道这听起来很蠢，但大多数问题都有权重和价值元素，我无法将这些问题与书籍和页面联系起来（也许是因为我的英语太差了），所以我不知道如何将这些解决方案应用到自己的问题上。 - Jason Kur

刚才编辑：@Kaganar，您指定页面是因为您将书籍在作者之间共享，目的是让每个作者复制的页面数量尽可能少。 - Jason Kur

那么... "每本书都有U页"这个说法不是真的吗？ - Kaganar

Answer 1

您可以在答案上进行二分查找。选择一个作者最多需要完成的书籍数量最大值，比如说 M，然后从左到右扫描书籍数组，为每个作者分配尽可能多的书籍，而不超过 M。如果还有剩余的书籍，则必须增加 M。 如果您已经成功分配了所有书籍，请减少 M。

- Keith Randall

---

我之前看过这个作为一个有效的答案，只是我的编程技能不够好，无法做出那样精细的东西。 - Aki K

你能否给我更多关于如何实现这个的细节？ - Jason Kur

选择一个 M。从 1 开始都可以。从书堆的顶部开始，将书分配给第一位作者。继续为第一位作者分配书籍，每次分配一本，直到下一本书将使第一位作者分配超过 M 页。第一位作者完成后，再从第二位作者开始。以此类推。如果您成功分配了所有书籍，则 M++ 并重试。如果您有剩余的书籍，则 M-- 并重试。 - Keith Randall

Answer 2

这被称为划分问题的优化版本。它是NP-难的。关于此问题，也有一篇相当精妙的文章。据我所知，有很多启发式算法可以近似解决它，但没有一种方法明确地设计为“在得到精确答案的同时走捷径”。

我以前遇到过类似的问题，我的实际实现最终成为了一种启发式方法（贪心方法对任意数量的划分都很容易应用），然后进行了几次优化迭代（尝试在集合之间交换/移动一些权重），每次优化后都会检查是否可以提前退出，如果解决方案不可能更好（p页给w个作者意味着p/w页每个作者是最优的，尽管如果w不能完全整除p，则p/w+1是最优的）。在您的情况下，由于您正在寻找精确解，因此最终需要备用暴力破解。

请注意，您只需回答其中一个分区的最大总和即可。这本身就是NP-hard问题--知道更少的信息不过是一个常数因子的快捷方式。

如果我是你，我会采用暴力破解的方式。对于少量书籍（不到十到二十本）和大页数（100到1000页），接近p/w可能不可行，以达到提前退出条件。另一方面，如果你需要处理任意数量的书籍，则可以在小尺寸上使用暴力破解，在大尺寸上进行近似处理。

- Kaganar

---

我实际上尝试过按作者分页的解决方案，如果不能完全整除，那么它就没有任何作用。 - Jason Kur