Là một bài tập về nhà, tôi có chương trình sau để thực hiện trong java:thuật toán biến đổi knapsack
Trong một tủ sách, chúng tôi có một ngăn N sách được sao chép bằng tay. Mỗi cuốn sách có các trang Ui nơi Ai là cuốn sách.
Chúng tôi cần cung cấp cho mỗi người viết sách liên tục từ ngăn xếp và chúng tôi không thể chia nhỏ các trang của một cuốn sách.
Tạo một chương trình sẽ cung cấp sách cho người viết nhưng bằng cách thu nhỏ số trang tối đa mà người viết sẽ sao chép.
Là đầu vào, người dùng sẽ cung cấp một chuỗi số, trong đó số đầu tiên là số lượng sách N và số thứ hai là số lượng nhà văn K và số còn lại là số trang mà mỗi cuốn sách có .
Là đầu ra, chương trình sẽ xuất ra cho người dùng số trang tối đa mà người viết sẽ sao chép.
Ví dụ:
Input: 15 6 30 40 10 40 50 20 30 40 10 70 10 50 30 50 10
Output: 90
Trong ví dụ này, nhà văn đầu tiên có thể mất Book1 = 30 và book2 = 40 nhưng không thể lấy ví dụ book1 = 30 với book3 = 10. Nói cách khác, bạn chỉ lấy sách từ đầu ngăn xếp mà không trộn chúng lên.
Đây là triển khai thực hiện của tôi:
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;
}
}
Những gì tôi làm mỗi khi tôi hợp nhất với nhau là cặp tối thiểu của cuốn sách cho đến khi chiều dài của danh sách của tôi là bằng với số nhà văn nhưng nó không hoạt động, trong ví dụ thay vì 90 nó xuất ra 100.
Tôi đã nghe về các giải pháp Lập trình động và các giải pháp tàn bạo đối với ba lô như các vấn đề nhưng trong trường đại học của tôi, họ chưa dạy chúng tôi về Lập trình động về những gì chúng ta biết hoặc anh ta muốn chúng ta tìm ra một giải pháp tàn bạo. Tôi chắc chắn giải pháp của tôi sẽ hoạt động nhưng vì một lý do nào đó nó không có, nếu bạn có thể chỉ cho tôi những lời khuyên trong một giải pháp khác ở đây hoặc nơi tôi đã nhầm lẫn, tôi sẽ rất vui.
Bạn có thể hướng tôi đến các giải pháp DP hoặc giải pháp tàn bạo nhưng trong trường hợp bạn hướng tôi đến các giải pháp DP, hãy cẩn thận rằng tôi hầu như không có ý tưởng về việc triển khai DP.
EDIT: Tôi đã xem xét một số các bài toán xếp ba lô giống như nhưng tôi không thể tìm thấy một với sự thay đổi này và một giải pháp phi DP mà tôi đã có thể hiểu
Tôi có thể thấy một vài giải pháp ở đây. –
g13n
@ g13n Tôi nhìn một số vấn đề giống như ba lô trong trang này nhưng tôi không thể tìm thấy biến thể cụ thể này, đặc biệt là nếu không có giải pháp DP –
Bạn đã xem các câu hỏi liên quan đến máy của mình chưa, tôi có thể thấy một loạt các giải pháp bruteforce ;-) – g13n