알고리즘 배낭문제

가장 흔한 문제인 배낭문제는 다양한 문제 풀이법이 있습니다.

먼저 가장 쉽게 재귀로 풀어보겠습니다.

재귀는 내가 이재품을 살때와 안살때를 재귀함수로 구현해주면됩니다.

int ws[] = { 3,4,1,2,3 }; //무게
int ps[] = { 2,3,2,3,6 }; //가치
int max = 10;

일단 간단하게 배낭크기를 10으로 잡고 5개의 물건이 있다고 보면됩니다.

//n 현재 반복 계수
//inter 현재 무게
int fn(int n, int inter) {
	if (n >= 5)return 0;
	if (inter >= max) return 0;
	return std::max(fn(n + 1, inter), fn(n + 1, inter + ws[n]) + ps[n]);
}
int main() {

	std::cout << fn(0, 0);
}

간단한 코드는 위와같다. 하지만 위의 코드는 계산했음에도 불구하고 계산할려는 특징이 있어 메모리로 계산을 했는지 안했는지 추가해야합니다. 이를 가지치기라고 하는데 다음에 설명하고 메모리DP를 풀겠습니다.

int ws[] = { 0,3,4,1,2,3 }; //무게
int ps[] = { 0,2,3,2,3,6 }; //가치
int max = 10;
int maxIn = 6;
int ret = 0;


int main() {
	int dp[6][11]{};

	for (int i = 1; i < 6; ++i) {
		for (int j = 0; j < 11; j++) {
			if (j - ws[i] < 0)
				dp[i][j] = dp[i - 1][j];
			else {
				dp[i][j] = std::max(dp[i-1][j], dp[i-1][j - ws[i]] + ps[i]);
			}

		}
	}
	std::cout << dp[5][10];
}

dp로 답을 구하는법은 엄청 간단하다 과거의 배낭의 무게를 가져올건지 과거에 특정 무게를 뺀 값을 가져올건지를 비교하면서 마지막에는 큰값이 나오게된다.