ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 한빛 알고리즘 chapter8 동적프로그래밍 조약돌놓기 문제
    최적화_통계_알고리즘/알고리즘 2012.07.16 00:43

    조약돌놓기 문제에서 서로 양립할 수 없는 패턴들에 대한 부분이 문제가 확장된다면 변경이 필요하겠네요....

    일단 책 기준으로해서 작성합니다...


    ----------------------------------------------------------------------------------------------------------

    public interface Pebble {


    public int pebble(int[][] dataA, int[][] resultA, int col, int pattern);

    }


    public interface PebbleBottomUp {


    public int pebble(int[][] dataA, int[][] resultA);


    }

    ----------------------------------------------------------------------------------------------------------
    //Top Down(Recursive)방식 
    public class DonghunPebble implements Pebble {

    //양립할 수 있는 패턴정보 배열 (문제의 row값이 변경이 되면 동적으로 변경할 필요있음)
    static int[][] availablePattern = {
    {1,2}, //0번 패턴  (1,2 패턴 양립가능)
    {0,2,3}, //1번 패턴  (0,2,3 패턴 양립가능)
    {0,1}, //2번 패턴  (2 패턴 양립 가능)
    {1} //3번 패턴  (1 패턴 양립가능)
    };
    @Override
    public int pebble(int[][] dataA, int[][] resultA, int col, int pattern) {

    int result = Integer.MIN_VALUE;
    if(col == 0){
    result = w(dataA, col, pattern);
    }else{
    //양립할 수 있는 패턴 추출
    int[] q = availablePattern[pattern];
    int tmp = 0;
    for(int i=0; i < q.length; i++){
    tmp = pebble(dataA, resultA, col-1, q[i]) +  w(dataA, col, pattern);
    if(tmp > result){
    result = tmp;
    }
    }
    }
    resultA[col][pattern] = result;//결과 검증용으로 중간단계 결과들 저장
    return result;
    }
    private int w(int[][] dataA, int i, int p){
    switch(p){
    case 0:
    return dataA[0][i];
    case 1:
    return dataA[1][i];
    case 2:
    return dataA[2][i];
    case 3:
    default:
    return dataA[0][i] + dataA[2][i];
    }
    }
    }
    ----------------------------------------------------------------------------------------------------------------------
    //Bottom Up방식 
    public class DonghunPebbleBottomUp implements PebbleBottomUp {

    //양립할 수 있는 패턴정보 배열 (문제의 row값이 변경이 되면 동적으로 변경할 필요있음)
    static int[][] availablePattern = {
    {1,2}, //0번 패턴  (1,2 패턴 양립가능)
    {0,2,3}, //1번 패턴  (0,2,3 패턴 양립가능)
    {0,1}, //2번 패턴  (2 패턴 양립 가능)
    {1} //3번 패턴  (1 패턴 양립가능)
    };

    @Override
    public int pebble(int[][] dataA, int[][] resultA) {

    //첫번째 열 데이터 설정
    for(int p=0; p < 4; p++){
    resultA[0][p] = w(dataA, 0, p);
    }
    int tmp = 0;
    int result = 0; 
    for(int i=1; i < dataA[0].length; i++){
    result = Integer.MIN_VALUE;
    for(int p=0; p < 4; p++){
    //p와 양립하는 패턴 q
    int[] q = availablePattern[p];
    tmp = maxPreviosValue(resultA, i-1, q) + w(dataA, i, p);
    resultA[i][p] = tmp;//결과저장
    if(tmp > result){
    result = tmp;
    }
    }
    }
    return result;
    }
    private int maxPreviosValue(int[][] resultA, int col, int[] q){
    int result = Integer.MIN_VALUE;
    int tmp = 0;
    for(int k=0; k < q.length; k++){
    tmp = resultA[col][q[k]];
    if(tmp > result){
    result = tmp;
    }
    }
    return result;
    }
    private int w(int[][] dataA, int i, int p){
    switch(p){
    case 0:
    return dataA[0][i];
    case 1:
    return dataA[1][i];
    case 2:
    return dataA[2][i];
    case 3:
    default:
    return dataA[0][i] + dataA[2][i];
    }
    }


    }
    -----------------------------------------------------------------------------------------------------------------------
    //Test Code
    public class DonghunPebbleTest {

    static int[][] dataA = {
    { 6,  7, 12, -5, 5,  3, 11, 3},
    {-8, 10, 14,  9, 7, 13,  8, 5},
    {11, 12,  7,  4, 8, -2,  9, 4}
    };

    @Test
    public void testPebble(){
    int[][] resultA = new int[8][4];//7개 열의 데이터, 4개 패턴 결과 용
    int result = Integer.MIN_VALUE;
    int tmp = 0;
    Pebble pebble = new DonghunPebble();
    for(int p=0; p < 4; p++){
    tmp = pebble.pebble(dataA, resultA, 7, p);
    if(tmp > result){
    result = tmp;
    }
    }
    System.out.println("result=" + result);
    Assert.assertEquals(106, result);
    print(resultA);
    }
    @Test
    public void testPebbleBottomUp(){
    int[][] resultA = new int[8][4];//7개 열의 데이터, 4개 패턴 결과 용
    int result = Integer.MIN_VALUE;
    PebbleBottomUp pebble = new DonghunPebbleBottomUp();
    result = pebble.pebble(dataA, resultA);
    System.out.println("result=" + result);
    Assert.assertEquals(106, result);
    print(resultA);
    }
    private void print(int[][] data){
    for(int i=0; i < data.length; i++){
    for(int j=0; j < data[0].length; j++){
    System.out.print(data[i][j] + " ");
    }
    System.out.print("\n");
    }
    }
    }

    댓글 0

Designed by Tistory.