최대이익 - 동적계획법

 

 

 

투자액	기업0	기업1	기업2
1	2	3	1
2	4	5	3
3	6	6	7
4	9	8	9

 

참고로 해당 이익표의 내용들을 아래와 같이 저장하였다. A[0,2] = 4 는 0기업에 2만원 투자했을 때의 이익이 4라는 것이다.

static int[][] r = {
        {0,2,4,6,9},
        {0,3,5,6,8},
        {0,1,3,7,9}
    };

 

쉽게 생각해서 max_return이라는 새로운 배열을 선언한고 해당 배열에는 최대값을 넣는다.

즉, max_return[1][2] = 3 이라고하면 0~1번 기업까지 2만원을 투자했을 때 얻을수있는 최대이익이 3 이라는 것이다.

max_return[1][2] 값을 구하기 위해서는 아래와 같은 과정이 필요하다. 

1) max_return[0][0] + r[1][2]

2) max_return[0][1] + r[1][1]

3) max_return[0][2] + r[1][0]

각 단계에서 구한 값 중에서 가장 큰 값이 max_return[1][2]에 들어가게 되는 것이다.

 

 

 

 

코드

package org.kyhslam.algo;

public class max_profit {

    static int[][] r = {
                        {0,2,4,6,9}, //기업 0
                        {0,3,5,6,8}, //기업 1
                        {0,1,3,7,9}
                };

    static int[][] max_return = new int[6][6];


    // m : 투자금액
    // n : 기업 수
    public static void calculate(int n, int m){

        int i =0;
        int j =0;
        int k=0;
        int max =0;
        int t = 0;
        for(i=0; i <= m; i++){
            max_return[0][i] = r[0][i];
        }

        System.out.println("초기화");
        view(max_return);
        System.out.println("초기화 끝");


        for(i=1; i <= n; i++){

            System.out.println();

            for(j=1; j <= m; j++){
                max = -1;
                System.out.printf("i : " + i +  " , j : " + j);
                System.out.println();
                for(k=0; k <= j; k++){
                    t = max_return[i-1][k] + r[i][j-k];
                    System.out.println(" --- max_return[" + (i-1) + "][" + k + "] + "  + "r[" + i + "][" + (j-k) + "]");
                    System.out.println(" *** " + max_return[i-1][k] +  " + " + r[i][j-k]);
                    if(t > max){
                        max = t;
                    }
                }
                System.out.println("*** insert max == : " + max);
                max_return[i][j] = max;
                view(max_return);
            }
        }
    }


    public static void main(String[] args) {
        calculate(2,4);
        System.out.println(max_return[1][3]);
        System.out.println();

        System.out.println("final ==============");
        view(max_return);
        System.out.println();
        System.out.println("max == " + max_return[2][4]);
        //System.out.println(profit(2,2));

    }

    public static void view(int [][] arr){
        for(int i=0; i < arr.length; i++){

            for(int j=0; j < arr[i].length; j++){
                System.out.printf(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

}