#include "..\CookHeader.h"

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