5

作为一项家庭作业，我有以下程序要在 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

在此示例中，第一个作者可以取 book1 = 30 和 book2 = 40，但不能取例如 book1 = 30 和 book3 = 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;
}
}

我所做的是每次我将最小的一对书合并在一起，直到我的列表长度等于作者的数量但它不起作用，在示例中而不是 90 它输出 100。

我听说过动态编程解决方案和背包类问题的残酷解决方案，但在我的大学里，他们还没有教我们动态编程，所以教授要么对我们所知道的感到困惑，要么他希望我们找到一个残酷的解决方案。

我确信我的解决方案会起作用，但由于某种原因它不起作用，如果你能在这个或我弄错的地方向我指出另一个解决方案的提示，我会很高兴。

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

编辑：我已经看过一些类似背包的问题，​​但我找不到具有这种变化的问题和我能够理解的非 DP 解决方案

4

2 回答 2

2

您可以对答案进行二进制搜索。选择一个作家的最大值，比如说M，然后从左到右扫描书籍数组，为每个作家分配尽可能多的书，但不超过M。如果还有书，那么你必须增加M。如果您已成功分配所有书籍，请减少M.

于 2012-04-30T16:17:51.003 回答
0

这被称为分区问题的优化版本。它是 NP 难的。还有一篇关于它的相当巧妙的文章。据我所知，有很多启发式方法可以逼近它，但没有明确设计用于“走捷径”同时获得准确答案的方法。

我之前遇到过类似的问题，我的实际实现最终成为一种启发式方法（贪婪方法适用于任意数量的分区很简单），然后进行了几次优化迭代（尝试在设置）在每次优化后检查是否解决方案可能更好（w 写入器的 p 页意味着每个写入器的 p/w 页是最佳的，尽管如果 w 不完全除 p p/ w+1 是最优的）。在您的情况下，由于您正在寻找一个精确的解决方案，您最终将需要一个支持暴力破解的案例。

请注意，您只是被询问其中一个分区的最大总和是多少。这实际上是 NP-hard 本身——知道更少的信息只不过是一个常数因子捷径。

如果我是你，我只会用蛮力。对于少量书籍（少于 10 到 20 页）和大量页数（100 到 1000），接近 p/w 很可能无法达到提前退出的条件。另一方面，如果您需要处理任意数量的书籍，则对小尺寸使用蛮力，对较大尺寸使用近似值。

于 2012-04-30T16:37:24.123 回答