냅색 문제
KnapSack문제의 유형
크냅색
각 물건별로 value와 weight가 주어지고, 이 값에 맞추서 배낭에 물건을 넣어서 가장 가치가 높은 경우를 찾아내는 문제이다.
모든 경우의 수를 넣어본다
이는 Brute-Force로 푸는 방법이다. 다만 이는 2^n시간복잡도를 가지고, 아마 이렇게 푸는 일은 없을것이다.
가치가 높은것부터 넣는다
이는 그리디 방식으로 푸는것이다. 다만 항상 최적의 결과를 보장하지 못한다.
Fractional Knapsack이라고 불리는 물건을 잘라서 넣을 수 있는 문제는 이런 방식으로도 풀 수 있다.
문제
4 7
6 13
4 8
3 6
5 12
문제에서의 배낭에는 총 7의 무개를 버틸 수 있는 가방과 4개의 품목이 주어진다.
이때, dp를 다음과 같이 정의한다.
dp[i][j] = 처음부터 i번째 까지의 물건을 살펴보고, 배낭의 용량이 j일때 배낭에 들어가는 최대가치의 합이다.
- i번째 물건의 무개는 w[i]이고, 가치는 v[i]이다.
- 가방에 i번째 물건을 넣지 않았을때 가치의 최대합은 dp[i-1][j]이다.
- 만약 i번째 물건을 넣었다면, dp[i-1]j-w[i]] + v[i]가 그 최대값이 될 것이다.
예를 들어 dp[3][6] (3번째 물건까지 봄, 6이 배낭의 용량) 일때,
- MAX(dp[2][6], dp[2]6-w[3]] + v[3]) 이다.
전체 코드
#include <iostream>
#include <algorithm>
using namespace std;
int w[101];
int v[101];
int dp[101][100001];
int n, k;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (j - w[i] >= 0) { // 만약 무게한도 내라면
dp[i][j] = max(dp[i-1][j], dp[ i- 1][j - w[i]] + v[i]); // 점화식
} else{
dp[i][j] = dp[i-1][j]; // 아니라면 이전값
}
}
}
cout << dp[n][k];
}
Author And Source
이 문제에 관하여(냅색 문제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@blacklandbird/냅색-문제저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)