Javaで動的計画法を使い、最大利益と派遣数を表示したい

Question

前提・実現したいこと

Javaで動的計算法を使い、3つの地域に人を分けて配置し、地域ごとの最適な配置数とその時に利益を表示するプログラムについてです。
3つの地域はそれぞれ
tiiki0 人数0　1　2　3　4　5　6　7
利益3　5　8　9　10　13　15　18

tiiki1 人数0 1 2 3 4 5 6 7
利益2 4 6 8 10 11 12 12

tiiki2 人数0 1 2 3 4 5 6 7
利益4 6 8 11 12 13 13 14
と人数と利益の関係は判明しています。
例としては　総人数が0の場合
tiiki0
人数0　利益3
tiiki1
人数0　利益2＋3＝5
tiiki2
人数0　利益2＋3＋4＝9
のような具合です。

これは派遣数と利益の関係になります
tiiki0_haken 表
総人数　　　　　0　1　2　3　4　5　6　7
利益　　　　　3　5　8　9　10　13　15　18
地域0への派遣数0　1　2　3　4　5　6　7
tiiki1_haken 表
総人数　　　　　0　1　2　3　4　5　6　7
利益　　　　　5　7　10　12　14　16　18　20
地域0への派遣数0　0　0　1　2　3　4　0
tiiki2_haken 表
総人数　　　　　0　1　2　3　4　5　6　7
利益　　　　　9　11　14　16　18　21　23 25
地域0への派遣数0　0　0　0　0　3　3　3

私が今回表示したいのはtiiki2_haken表です。
表示する形としては
9　11　14　16　18　21　23 25
0　0　0　0　0　3　3　3
のようにしたいです

発生している問題・エラーメッセージ

6 8 10 13 15 17 19 21
0 0 0 3 3 3 3 3
と表示される答えが違う

該当のソースコード

public class Report1401 {
public static void main(String[] args) {
	int[] tiiki0_rieki = {3, 5, 8, 9, 10, 13, 15, 18};
	int[] tiiki1_rieki = {2, 4, 6, 8, 10, 11, 12, 12};
	int[] tiiki2_rieki = {4, 6, 8, 11, 12, 13, 13, 14};
	int[][] tiiki0_haken = new int[2][8];
	int[][] tiiki1_haken = new int[2][8];
	int[][] tiiki2_haken = new int[2][8];

    for (int total = 0; total < 8; total++) {
         tiiki0_haken[0][total] = tiiki0_rieki[total];
}
          for (int total = 0; total < 8; total++) {
               tiiki0_haken[1][total] = total;
}
    for (int total = 0; total < 8; total++) {
	for (int tiiki1sousu = 0; tiiki1sousu <= total; tiiki1sousu++){
	
        int rieki = tiiki1_rieki[tiiki1sousu] + tiiki0_rieki[total - tiiki1sousu];
             if (tiiki1_haken[0][total] < rieki) {
		tiiki1_haken[0][total] = rieki;
		tiiki1_haken[1][total] = tiiki1sousu;
       }
      }
 }
      **for(int total = 0; total < 8; total++) {
          for (int tiiki2sousu = 0; tiiki2sousu <= total; tiiki2sousu++){     
       
       int rieki = tiiki2_rieki[tiiki2sousu] + tiiki1_rieki[total - tiiki2sousu];
             if (tiiki2_haken[0][total] < rieki) {
		tiiki2_haken[0][total] = rieki;
		tiiki2_haken[1][total] = tiiki2sousu;
		}
	}
}**
for (int[] is : tiiki2_haken) {
for (int i : is) {
System..print(i + " ");
}
System.out.println();
}
}
}

試したこと

tiiki1_haken 表
5　7　10　12　14　16　18　20
0　0　0　1　2　3　4　0
を表示するプログラムに追記すればよいと言われたので太文字の部分を追加してみましたが上手くいきません
どうか教えていただけないでしょうか

補足情報（FW/ツールのバージョンなど）

手順としては
1.まず地域0のみを考えて、地域0への派遣数に応じた利益を表にまとめる
2.次に地域１と地域０のみを考えて総人数（０～７人）ごとの最大利益とそのときの地域１への派遣数を表にまとめる
3.最後に3つの地域を全て考えて総人数（０～７人）ごとの最大利益とそのときの地域２への派遣数を表にまとめる。
といった形で2まで出来たと思います

Answer 1

蛇足です.
問題を細分化するという点で動的計画法っぽいでしょうか.

public class Report1401 {

    static final int TOTAL_MAX = 8;

    public static void main(String[] args) {
        // calculate/print の組を増やせば地域をいくらでも増やせます

        //地域0 - 地域0の利益からそのまま格納
        int[][] tiiki0_haken = calculate(new int[]{3, 5, 8, 9, 10, 13, 15, 18}, null);
        print("地域0", tiiki0_haken);

        //地域1 - 地域1の利益と地域0の派遣データから計算
        int[][] tiiki1_haken = calculate(new int[]{2, 4, 6, 8, 10, 11, 12, 12}, tiiki0_haken);
        print("地域1", tiiki1_haken);

        //地域2 - 地域2の利益と地域1の派遣データから計算
        int[][] tiiki2_haken = calculate(new int[]{4, 6, 8, 11, 12, 13, 13, 14}, tiiki1_haken);
        print("地域2", tiiki2_haken);
    }

    //派遣表を計算
    static int[][] calculate(int[] tiiki_rieki, int[][] old_haken) {
        int[][] new_haken = new int[2][TOTAL_MAX];
        for(int total = 0; total < TOTAL_MAX; total++) {
            if(old_haken == null) {
                new_haken[0][total] = tiiki_rieki[total];
                new_haken[1][total] = total;
            } else {
                for (int sousu = 0; sousu <= total; sousu++){
                    int rieki = tiiki_rieki[sousu] + old_haken[0][total - sousu];
                    if (new_haken[0][total] < rieki) {
                        new_haken[0][total] = rieki;
                        new_haken[1][total] = sousu;
                    }
                }
            }
        }
        return new_haken;
    }

    //派遣表を表示
    static void print(String title, int[][] haken) {
        System.out.println(title);
        for (int[] is : haken) {
            for (int i : is) System.out.printf("%2d ", i);
            System.out.println();
        }
    }
}

Comments

[kurikuri]

補足ありがとうございます！
こういう書き方あるんですね・・・
これからもっと理解できるように頑張っていきます！

[jimbe]

補足ではなくて蛇足です^^;
プログラムの書き方や作り方は個性が出ます. 仕事上では個性を出すと他の人がメンテナンスし辛くなるので怒られてしまいますが, 個人的な時にはつい 'あーも出来る, こーも出来る, いやこうやったら(綺麗|短い|早い|面白い|etc)かな?' と延々と弄っていまいます^^

Answer 2

前回の質問から来ました。
アルゴリズムに関しては、質を問わないでください笑
単にforを回して網羅しているだけです。

for(int total=0;total<8;total++){
   for(int num2=0;num2<=total;total++){
       for(int num1=0;num1<=(total-num2);num1++){
           int rieki=tiiki2_rieki[num2]+tiiki1_rieki[num1]+tiiki0_rieki[total-num2-num1];
                if(tiiki2_haken[0][total]<rieki){
                       tiiki2_haken[0][total]=rieki;
                       tiiki2_haken[1][total]=num2;
                }
       }
   }
}

ここでの num1 は地域１の人数、num2 は地域2の人数です。
私のほうで出力は9,11,14、…　と0,0,0,0,0,3,…を確認済みです。
teratailは宿題の外注と思われないためにも、下は必ず読んで自身のスキルアップに取り入れてください。
★考え方
まず、総人数を仮に3とすれば、人数の振り分けは10通りになる。
なぜ10通りなのかは、樹形図でも描けば分かります。

　地域2,地域1,地域0
   0-0-3
     1-2
     2-1
     3-0
   1-0-2
     1-1
     2-0
   2-0-1
     1-0
   3-0-0

これら10通りの利益を計算し、最大のものを tiiki2_haken[0][3]に代入すればいい。
樹形図を見れば、
地域2の人数はforで0から総人数まで回す
地域1の人数はforで0から（総人数－地域2人数）まで回す
地域0の人数は地域1の人数とone-to-one対応するので分岐の必要なし

こんな感じで作りました。
10通りの中に、同じ最大値を持つものが複数でてきます。（総数3以外の場合でも）
上だと、0-1-2と2-0-1の組などはいずれも最大値16になります。
しかし地域2への派遣人数を0で出力するには、0-1-2の組でtiiki2_haken[1][3]を確定しなければなりません。
そのため、forは地域2から先に回しています。
最も内側のifは、「計算した利益が最大値を更新した場合」に配列を更新する仕組みなので、
0-1-2の組を後に回すと最大値を更新できずに、tiiki2_haken[1][3]=0になりません。

もっと素晴らしいアルゴリズムがでてきたら、そちらも学んでみてください。

Comments

[Kota_Kappa]

失礼しました。
動的計画法、でしたね。
であればこの方法では学習の主旨がちがうことになります。
地域0と地域1での最適解が、
地域2も含めた全地域で最適になるとは限らないから、たとえば3人なら
●tiiki1haken[0][2](←2人の場合の最大利益)にtiiki2rieki[1]を足したもの
●tiiki1haken[0][1](←1人の場合の最大利益)にtiiki2rieki[2]を足したもの
●tiiki1haken[0][0](←0人の場合の最大利益)にtiiki2rieki[3]を足したもの

これら3つのなかの最大が、tiiki2haken[0][3]になるといったコードにする感じなのでしょう。
そこに漸化式を使うと。

[kurikuri]

回答ありがとうございます。
問題点を指摘していただき、ありがとうございます
いずれ計算を重ね行けば起こりうるミスもあると思いますので、参考にさせていただきます！
本当にありがとうございました

Answer 3

利益を計算するときの, 参照する表が違います.

//地域1の利益を計算する部分
int rieki = tiiki1_rieki[tiiki1sousu] + tiiki0_rieki[total - tiiki1sousu];

//地域2の利益を計算する部分
int rieki = tiiki2_rieki[tiiki2sousu] + tiiki1_rieki[total - tiiki2sousu];

と, 利益を算出する際に自分の地域の rieki と一つ前の地域の rieki を足していますが, 一つ前の地域の利益は(計算で出した) haken のほうでなければなりません.
つまり

//地域1の利益を計算する部分
int rieki = tiiki1_rieki[tiiki1sousu] + tiiki0_haken[0][total - tiiki1sousu];

//地域2の利益を計算する部分
int rieki = tiiki2_rieki[tiiki2sousu] + tiiki1_haken[0][total - tiiki2sousu];

です.
地域1の計算のほうでは tiiki0_rieki[] も tiiki0_haken[0][] も同じ値なので分かり難かったですね.

Comments

[kurikuri]

回答ありがとうございます！
無事表示することが出来ました。
自分の注意不足で手間を取らせてしまい、申し訳ございません。
riekiとhakenをしっかりと見ておくべきでした・・・
本当にありがとうございました！

Answer 4

たぶんエラーがわからないから止まっているのだと解釈して回答します。

（エラー文の通りですが）配列の書き方をしているのがint型のためにエラーとなっています。

... + rieki[total - tiiki2sousu];

このriekiという変数はint型なのではないですか？

適切な変数に変えてあげればエラーは取れるかと思います。

Comments

[kurikuri]

回答ありがとうございます！
初心者ですいません
適切な変数としてどのようなものがありますか?

[dice142]

配列として宣言している変数が適切ですね。

[kurikuri]

ありがとうございます！エラーは出ませんでしたが表示される答えが違いました、、、
6 8 10 13 15 17 19 21
0 0 0 3 3 3 3 3
と出てしまいます
、、、

[退会済みユーザー]

アルゴリズムの話を読み解いたりして突っ込みたくないんで感覚的に…。

「3.最後に3つの地域を全て考えて...最大利益とそのときの地域２への派遣数」に対して、修正された下記コードでの計算は意味が合っていると思いますか？
tiiki2_rieki[tiiki2sousu] + tiiki1_rieki[total - tiiki2sousu];

[kurikuri]

回答ありがとうございます！
そのコードではtiiki0の計算が出来てないですよね、、、
この場合はtiiki0_riekiの計算を追加しないといけないですよね？
その場合は+で繋げていいんでしょうか？

[退会済みユーザー]

やってみた方が早いと思いますが、+で繋げばいいです。よくわからなければ、次の行で、rieki = rieki + tiiki0_rieki[...略]でもいいんじゃないですか。

でもきっと違う変数を使いたいんじゃないかな…。

繰り返しますが、アルゴリズムについては読み解いていません。アルゴリズムとロジックが一致しているかは熟考しない感覚的な返答です。

とか、JavaのコードはHello Worldしか書いたことない人が偉そうなこと言ってます。

[kurikuri]

いえ、大変ありがたい意見でした！
もう少し、考えてみます！
回答ありがとうございます！