揹包變型算法

Question

作爲一門功課，我有以下程序用Java做：

書櫃，我們有哪些必須由專人用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的解決方案，我能理解

Answer 1

你可以做的二進制搜索回答。爲作家選擇最大數量，例如M，然後從左到右掃描書籍數組，然後爲每位作者分配最多的書籍，而不超過M。如果有任何書籍，則必須增加M。如果您已成功分配所有書籍，請減少M。

Answer 2

這被稱爲partition problem的優化版本。這是NP-Hard。關於它也有相當的slick article。據我所知，有很多啓發式方法來逼近它，但沒有明確的設計方法來「確定捷徑」，同時找到確切的答案。

我以前遇到類似的問題，我的實際實現最終成爲一種啓發式方法（貪婪方法適用於任意數量的分區），然後進行幾次迭代優化（嘗試交換/移動如果解決方案不可能更好，每個優化之後的每個優化之後的一個檢查將會帶有一個檢查（對於編寫者來說p頁意味着每個編寫者的p/w頁是最優的，但是如果w不劃分p完全是p/w + 1是最優的）。在你的情況下，因爲你正在尋找一個確切的解決方案，你最終需要一個備份案例。

請注意，您只需要詢問其中一個分區的最大總和是多少。實際上，這實際上是NP-hard--知道較少的信息不僅僅是一個常數因子的捷徑。

如果我是你，我只是蠻橫的逼迫它。有了少量的書籍（少於十到二十）和較大的頁數（100到1000），靠近p/w不太可能達到早期狀態。另一方面，如果您需要處理任何數量的書籍，那麼對於較小尺寸的文件可能具有蠻力，而對於較大尺寸文件則可以近似。