背包变化算法 [英] knapsack variation algorithm

问题描述

作为一门功课，我有以下方案，使在Java中：

As a homework I have the following program to make in java:

在一个书柜，我们有一叠N个书这不得不用手复制被K的作家。 每本书都有UI页面其中A是书。

In a bookcase we have a stack of N books which have to be copied by hand by K writers. Each book has Ui pages where Ai is the book.

我们需要从堆栈中给每个作家连续书籍，我们可以不拆的书页。

We need to give each writer continuous books from the stack and we can't split the pages of a book.

请一个程序，它会向作家，但通过最小化的页面作家将复制的最大数量给予的书籍。

Make a program which will give books to the writers but by minimizing the maximum number of pages a writer will copy.

作为输入的用户将给出的数字，其中第一个数字是书籍N和所述第二数目的数目是作家数目K和数字的其余部分的每个页面的书具有数字的字符串。

As an input the user will give a string of numbers, where the first number is the number of books N and the second number is the number of writers K and the rest of the numbers are the number of pages each books has.

作为输出程序将输出给用户的最大页数作家将复制。

As an output the program will output to the user the maximum number of pages a writer will copy.

例如：

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

Input: 15 6 30 40 10 40 50 20 30 40 10 70 10 50 30 50 10
Output: 90

在这个例子中，第一个作家可以采取第一册= 30和Book = 40，但不能采取如第一册= 30与book3 = 10.在你只需要从堆栈的顶部书没有把它们组合起来等字样。

In this example the first writer can take book1 = 30 and book2 = 40 but cannot take for example book1 = 30 with book3 = 10. In other words you take books only from the top of the stack without mixing them up.

下面是我的实现：

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。

What I do is each time I merge together the minimal pair of books until the length of my list is equal to the number of writers but it doesn't work, in the example instead of 90 it outputs 100.

我听说过动态规划解决方案和残酷的解决方案，以背包一样的问题，但在我的大学，他们还没有告诉我们还没有关于动态规划，因此无论是教授是困惑我们所知道的，否则他希望我们能够找到一个残酷的解决方案。

I've heard about Dynamic Programming solutions and Brutal solutions to knapsack like problems but in my university they haven't taught us yet about Dynamic Programming, so either the professor is confused about what we know or he wants us to find a brutal solution.

我确信我的解决方案，将工作，但由于某种原因，它只是没有，如果你能提示点我在这个或其他解决方案，我一直误以为我会很高兴。

I was sure my solution would work but for some reason it just doesn't, if you could point me with tips in another solution in this or where I have been mistaken I would be very glad.

您可以任你点我对DP解决方案要注意，我几乎不知道关于DP实现点我对DP解决方案，或残酷的解决方案，但以防万一。

You can either point me towards DP solutions or Brutal solutions but in case you point me towards DP solutions beware that I have almost no idea about DP implementation.

编辑：我已经看了一些背包类问题，但我无法找到一个具有这种变化和非-DP的解决方案，我能COM prehend

I have already looked at some of the knapsack-like problems but I could not find one with this variation and a non-DP solution that I was able to comprehend

推荐答案

您可以做在答题二进制搜索。选择一个最大的作家做，说 M ，然后扫描书籍阵列由左到右，分配每个作家的大多数书籍，你可以在不超过<$ C $ ç> M 。如果还留有什么书，那么你就必须增加 M 。如果你已经成功地分配所有的书，降低 M 。

You could do binary search on the answer. Pick a maximum for a writer to do, say M, and then scan the book array from left to right, assigning each writer the most books you can without exceeding M. If there are any books left, then you must increase M. If you've successfully assigned all the books, decrease M.

这篇关于背包变化算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！