ナップザック変動アルゴリズム私はJavaで作成するには、次のプログラムを持っている宿題として

Question

：

我々はKの作家の手でコピーする必要がN本のスタックを持って本棚に。 各書籍には、Aiが書籍であるUiページがあります。

各ライターにスタックから連続した書籍を渡す必要があります。書籍のページを分割することはできません。

ライターがコピーする最大ページ数を最小限に抑えることによって、ライターに書籍を提供するプログラムを作成します。

入力として、最初の数字は書籍Nの数であり、2番目の数字はライターKの数で残りの数字は各書籍のページ数です。

出力として、プログラムは、ライターがコピーする最大ページ数をユーザーに出力します。

例：

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

この例では最初のライターは、BOOK1を取ることができる= 30とbook2 = 40しかしbook3 = 10ではbook1 = 30を取ることはできません。言い換えれば、スタックの上端からのみ本を取ります。ここで

は私の実装です：私のリストの長さは、作家の数と同じですが、それが動作しないまで、私は何をすべきか

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ソリューションまたは残忍なソリューションを指摘することができますが、DPソリューションに向けて私を指摘する場合は、DP実装についてほとんど気づかないことに注意してください。

編集：私はすでにナップサックのような問題のいくつかを見てきましたが、私はこの変化と、私はあなたが上のバイナリ検索を行うことができ

Answer 1

理解することができた非DPソリューションを持つものを見つけることができませんでした回答。作者のために最大のものを選んでください。たとえば、Mを入力してから、左から右に向かって書籍の配列をスキャンし、各作家にMを超えることなくできる最大の本を割り当てます。書籍が残っている場合は、Mを増やす必要があります。すべての書籍を割り当てた場合は、Mを減らしてください。

Answer 2

これはpartition problemの最適化バージョンとして知られています。それはNP-Hardです。むしろそれについてもslick articleがあります。私が知る限り、それを近似するためのヒューリスティックは数多くありますが、正確な解答に至るまでの間、「短期間で」と明示的に設計された方法はありません。

私はこれまでと同様の問題を抱えていました。私の実際的な実装はヒューリスティックな方法でした（欲張りの方法は任意の数のパーティションに適用するのが簡単です）。そして、最適化を数回繰り返します各最適化の後にチェックを入れて、早く解決することができれば解決策がそれほど良くないことはありません（wページのページはライターごとにp/wページが最適ですが、wが分割されていない場合pは正確にp/w + 1が最適です）。あなたの場合、正確な解決策を探しているので、究極的にはブルートフォースのバックアップケースが必要になります。

パーティションのうち最大のものがどれだけあるかを尋ねられます。これは実際にはNP自体ではありません。情報が少ないことが、一定の要素のショートカット以上のものではないことが分かっています。

私があなただったら、私はそれを強制します。小さい本数（10から20未満）と大きなページ数（100から1000）では、早期終了条件に合うようにp/wに近づくことができない場合があります。一方、何冊かの本を扱う必要がある場合は、小さなサイズの場合は強引にし、大きいサイズの場合は近似します。