作为一项作业,我需要用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。换句话说,你只能从书堆的顶部选书而不混淆它们。
以下是我的实现:
我每次将书籍的最小配对合并,直到列表的长度等于作家数量为止,但这种方法不起作用,在这个例子中输出的是100而不是90。
我听说过动态规划解决背包问题的方案和暴力解决方案,但在我的大学里他们还没有教我们动态规划,所以无论是教授混淆了我们知道的内容还是他想让我们找到一个暴力解决方案。
我确信我的解决方案能够起作用,但出于某些原因它就是不起作用,如果您能指点我其他解决方案的提示,无论是在这个问题上还是在哪里我会很高兴。
您可以向我指出DP解决方案或者暴力解决方案,但是请注意,如果您指向DP解决方案,我几乎对DP实施一无所知。
编辑:我已经看过一些类似于背包问题的问题,但我找不到一个带有这个变化的问题和一个我能理解的非DP解决方案。
在书架上有一叠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解决方案。