#include "..\CookHeader.h"

int maxWeight = 7;      // 배낭 최대 무게
int rowCount = 4;       // 보석 숫자
Array <int> weight = { 0, 5, 3, 4, 6 };     // 보석 무게(0, 진주, 루비, 수정, 금괴)
Array <int> money = { 0, 12, 6, 8, 13 };    // 보석 가격(0, 진주, 루비, 수정, 금괴)

int knapsack() {
    println("## 메모이제이션 배열 ##");

    Array <Array <int>> memoAry;
    memoAry = emptyArray2(rowCount + 1, maxWeight + 1); // 빈 배열 준비

    for (int row = 1; row < rowCount + 1; row++) {
        print(to_string(row) + "개 -->");               // 1~4개(4회)
        for (int col = 1; col < maxWeight + 1; col++) { // 1col KG ~ 7col KG
            if (weight[row] > col) {  // 물건 무게가 열보다 크면 == 물건이 가방에 안 들어가면
                memoAry[row][col] = memoAry[row - 1][col];
            }
            else { // 물건이 가방에 들어가면
                int value1 = money[row] + memoAry[row - 1][col - weight[row]];
                int value2 = memoAry[row - 1][col];
                memoAry[row][col] = max(value1, value2);
            }
            printf("%3d", memoAry[row][col]);
        }
        println("");
    }
    return memoAry[rowCount][maxWeight];
}

int main() {
    int maxValue = knapsack();
    println("\n배낭에 담을 수 있는 보석의 최대 가격 -->" + to_string(maxValue) + "억 원");
}