[DP] 막대기, 최장공통부분수열, knapsack

package com.company;

public class Main {

    public static void main(String[] args) {

        int[][] item = {{1, 6, 10}, {2, 100, 20}, {3, 120, 30}};
//        int maxValue = knapsack(item, 50);
//        System.out.println("최대가치: " + maxValue);


        int[] rodPrice = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
//        System.out.println("2칸일때 최대이익: " + cutRod(rodPrice, 2));
//        System.out.println("3칸일때 최대이익: " + cutRod(rodPrice, 3));
//        System.out.println("4칸일때 최대이익: " + cutRod(rodPrice, 4));
//        System.out.println("7칸일때 최대이익: " + cutRod(rodPrice, 7));

        System.out.println( "LSC: " + LCS("ABCBDAB", "BDCABA") );

    }

    //최장공통부분수열 문제
    public static int LCS(String str1, String str2){

        System.out.println("받은값: " + str1 + " / " + str2);

        //결과값들을 저장해나가는 이차원배열
        int[][] lcs= new int[str1.length()][str2.length()];

        for(int i=0; i<str1.length(); i++){
            for(int j=0; j<str2.length(); j++){

                if(i==0 || j==0){ //둘중 하나가 한글자일때
                    if( str2.contains(str1.substring(0,1)) || str1.contains(str2.substring(0,1)) ){
                        lcs[i][j] = 1;
                    }else{
                        lcs[i][j] = 0;
                    }
                }else{

                    //끝 글자가 같을 때
                    if(str1.substring(i,i+1).equals(str2.substring(j,j+1))){
                        lcs[i][j] = lcs[i-1][j-1] +1;
                    }else{ //끝 글자가 다를 때
                        lcs[i][j] = Math.max( lcs[i-1][j], lcs[i][j-1]);
                    }

                }
            }//for(j)
        }//for(i)

        return lcs[str1.length()-1][str2.length()-1];
    }

    //len길이일때 가장 가치가 높은 길이
    public static int cutRod(int[] price, int len){

        //기록을 담당할 배열
        //k[i][j] 0~i까지 막대기 넣을수있고, 최대 j까지 넣을 수 있는 것 중에서 돈 제일 많이 받는 조합
        int[][] k = new int[price.length][len+1];

        //i는 0~9(총10개). i번째 막대의 길이는 i
        for(int i=0; i<price.length; i++){

            for(int j=0; j<=len; j++){

                if(i==0 || j==0){ //넣을막대없음 or 남은길이0
                    k[i][j] = 0;
                }else if( i>j ) { //남은 길이가 이번 막대에는 부족
                    k[i][j] = k[i-1][j];
                }else{ // 이번 막대를 넣은 경우와 안넣은 경우 두가지로 나누어서 비교
                    k[i][j] = Math.max( price[i] + k[i][j-i], k[i-1][j] );
                }

            }//for(j)
        }//for(i)

        for(int i=0; i<price.length; i++){
            for(int j=0; j<=len; j++){

                System.out.println("k["+i+"]["+j+"]= " + k[i][j] );
            }
        }
        return k[price.length-1][len];
    }

    // 0/1 knapsack
    public static int knapsack(int[][] item, int maxWeight){

        // 기록을 담당할 배열(memo)
        // k[물건(i)][남은무게(w)] = 물건 1~i만 사용해서 w인 가방에 넣는 조합 중 가치가 최대인 것.
        int[][] k = new int[item.length][maxWeight+1];


        //i는 물건, w는 무게
        for(int i=0; i<item.length; i++){

            for(int w=0; w<=maxWeight; w++){

                if(i==0 || w==0){ //더 넣을 물건이 없음 or 남은 공간이 없음
                    k[i][w] = 0;
                }else if( item[i][2] > w){ //넣을 물건의 무게가 남은 공간보다 크다 -> 못넣으니 그 이전의 조합을 그대로 이어감.
                    k[i][w] = k[i-1][w];
                }else{ //더 넣을 공간이 남을 경우, 그걸 넣었을때랑 안넣었을 때 중 더 가치가 높은것을 찾음
                    k[i][w] = Math.max( item[i][1] + k[i-1][w-item[i][2]], k[i-1][w] );
                }

            }//for(w)
        }//for(i)

        return k[item.length-1][maxWeight];
    }
}