입력:
10 696 7974 30 230 490 22 13 649 355 24 47 333 865 1342 0 107 12 145 42 713 21
오답 출력:
1414
정답 출력:
1415
12865번 - 평범한 배낭
모든 경우의 수를 생각하지 않아서 그런 것입니다.
모든 경우를 생각하는 코드는
#include
#include
#include
using namespace std;
int main() {
int N, K;
cin >> N >> K;
vector> items(N);
for (int i = 0; i < N; ++i)
cin >> items[i].first >> items[i].second;
vector dp(K + 1, 0);
for (int i = 0; i < N; ++i) {
int w = items[i].first;
int v = items[i].second;
for (int j = K; j >= w; --j)
dp[j] = max(dp[j], dp[j - w] + v);
}
cout << dp[K] << endl;
return 0;
}
위에 올라온 답변에 있는 코드가 답이긴 하지만 작성자님코드에서 틀린점을 알려드리겠습니다
getMaxv함수에서 조건만 맞으면 물건을 무조건 담고 있습니다. 이렇게 되면 앞에서 가벼운것으로 가방을 채우면 뒤에 있는 무겁지만 가치가 높은 것들이 무시될수 있습니다.
이를 위해서 선택할지 안할지에 대해서 경우를 나눠야 할것입니다.
하지만 단순히 경우를 나눠서 재귀를 돌리면 O(2^n)의 시간복잡도를 가지므로 비효율적입니다.
그래서 위 코드처럼보통은 DP(동적 계획법)을 사용해 상태 전이를 정의하고 중복 계산을 줄여 효율적으로 풉니다.
댓글을 작성하려면 로그인해야 합니다.
tenlemsp 1년 전
재귀함수 만들기는 했는데 이렇게 하는게 맞나요?
알고리즘도 이게 맞는지 모르겠고 ㅋㅋ 일단 예제로 하면 출력은 잘 나오는것 같긴한데 어렵네요...