Knapsack Code Review

1. Principle of the Algorithm

집합의 Power Sets를 구하는 문제에서 사용했던 State-Space Tree의 Backtracking 방법을 사용하면 된다.

매개변수는 현재 level을 나타내는 k, 현재까지의 무게 합 current_weight, 현재까지의 가치 합 current_value가 있다.

Base Case: Weight의 합이 Total Weight를 초과하였는지, 혹은 배낭에 넣은 아이템의 개수가 Total Number와 일치하는지 검사한다.

Recursion Case: 다음 아이템을 넣을지, 말지를 결정한다.

2. My Code

int knapsack(int k) {
	if (k == numberOfItems) {
		int sumOfItemWeights = 0;
		int sumOfItemValues = 0;

		// get the weight sum of selected items
		for (int i = 0; i < numberOfItems; i++) {
			if (selectedItems[i]) {
				sumOfItemWeights += itemWeight[i];
			}
		}

		if (sumOfItemWeights <= totalWeight) {
			// get the value sum of selected items
			for (int i = 0; i < numberOfItems; i++) {
				if (selectedItems[i]) {
					sumOfItemValues += itemValue[i];
				}
			}

			if (sumOfItemValues > maxValue) {
				maxValue = sumOfItemValues;
				// copy current selection
				for (int i = 0; i < numberOfItems; i++) {
					decidedItems[i] = selectedItems[i];
				}
			}
		}
	}
	
	else {
		selectedItems[k] = false;
		getSubset(k + 1);
		selectedItems[k] = true;
		getSubset(k + 1);
	}
}

2. Updated Code

int knapsack(int k, int cur_weight, int cur_value) {
	if (cur_weight > totalWeight) {
		return 0;
	}
	else if (k == numberOfItems) {
		if (cur_value > maxValue) {
			maxValue = cur_value;

			for (int i = 0; i < numberOfItems; i++) {
				decidedItems[i] = selectedItems[i];
			}
		}
	}
	else {
		selectedItems[k] = false;
		getSubset(k + 1, cur_weight, cur_value);
		selectedItems[k] = true;
		getSubset(k + 1, cur_weight + itemWeight[k], cur_value + itemValue[k]);
	}
}

3. Self Evaluation

• My Code는 (k == numberOfItems)라는 하나의 Base Case가 있고, 이것은 완성된 배낭에 있는 Item들의 가치의 총 합을 구한다.

• 이 경우는 Knapsack State-Space-Tree의 모든 leaves를 track한다.

• 그와 다르게 Updated Code는 두 개의 Base Case가 존재한다.

• Case 1는 current_weight가 totalWeight보다 크면 리턴한다. 즉, 굳이 모든 leaves를 track 안 해도 된다.

• Case 2는 배낭이 완성 됐을 때, maxValue를 구한다.

• Recursion Call에서 현재 level까지의 Item의 무게와 가치를 keep하기 위해 추가적인 매개변수 current_weight과 current_value를 사용했다.

4. Take-Home Message

• Backtracking을 사용할 때, 전제 조건을 만족하지 못하면 return하는 Base Case를 만들어서 tracking 횟수를 줄일 수 있다.
• 다음 Recursion Call에서 현재 변수의 데이터를 사용하고 싶으면 그 변수를 매개변수로 사용하면 된다.