5

宿題として、Javaで作成する次のプログラムがあります。

本棚には、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 を取得できますが、たとえば 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 ソリューションまたは残忍なソリューションのいずれかを指摘することができますが、DP ソリューションを指摘する場合は、DP の実装についてほとんど知らないことに注意してください。

EDIT：私はすでにナップザックのような問題のいくつかを見てきましたが、私が理解できたこのバリエーションと非DPソリューションを持つものを見つけることができませんでした

4

2 に答える 2

2

あなたは答えに対して二分探索をすることができます。たとえばM、ライターが実行できる最大数を選択してから、ブックアレイを左から右にスキャンし、各ライターに、を超えずに可能な限り多くの本を割り当てますM。本が残っている場合は、増やす必要がありMます。すべての本を正常に割り当てたら、を減らしMます。

于 2012-04-30T16:17:51.003 に答える
0

これは、分割問題の最適化バージョンとして知られています。NPハードです。それについてはかなり洗練された記事もあります。私が知る限り、それを概算するためのヒューリスティックはたくさんありますが、正確な答えを得るために「近道をする」ように明示的に設計された方法はありません。

私は以前にこれに似た問題を抱えていましたが、実際の実装はヒューリスティックな方法 (貪欲な方法は任意の数のパーティションに適用するのは簡単です) になり、最適化のいくつかの反復 (パーティション間でいくつかの重みを交換/移動してみてください)各最適化の後にチェックを行い、ソリューションがこれ以上改善されない可能性がある場合 (w ライターの p ページは、ライターごとの p/w ページが最適であることを意味しますが、w が p を正確に p/ で割らない場合) w+1 が最適です)。あなたの場合、正確な解決策を探しているので、最終的にブルートフォースのバックアップケースが必要になります.

パーティションの 1 つの最大合計がいくらかを尋ねられるだけであることに注意してください。これは実際には NP 困難そのものです。情報が少ないことを知っていることは、一定の因子の近道にすぎません。

私があなただったら、力ずくで攻撃します。本の数が少なく (10 から 20 未満)、ページ数が多い (100 から 1000) 場合、p/w に近づくことは、早期に終了する条件に達するのに十分な可能性があります。一方、任意の数の本を処理する必要がある場合は、小さいサイズの場合は力ずくで、大きいサイズの場合は近似値を使用します。

于 2012-04-30T16:37:24.123 に答える