tenlemsp   1년 전

재귀함수 만들기는 했는데 이렇게 하는게 맞나요?

알고리즘도 이게 맞는지 모르겠고 ㅋㅋ 일단 예제로 하면 출력은 잘 나오는것 같긴한데 어렵네요...

evan3233   1년 전

입력:

10 696
7974 30
230 490
22 13
649 355
24 47
333 865
1342 0
107 12
145 42
713 21

오답 출력:

1414

정답 출력:

1415

ohjoonsoo   1년 전

모든 경우의 수를 생각하지 않아서 그런 것입니다.

모든 경우를 생각하는 코드는

#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;
}

jtw7913   1년 전

위에 올라온 답변에 있는 코드가 답이긴 하지만 작성자님코드에서 틀린점을 알려드리겠습니다

getMaxv함수에서 조건만 맞으면 물건을 무조건 담고 있습니다. 이렇게 되면 앞에서 가벼운것으로 가방을 채우면 뒤에 있는 무겁지만 가치가 높은 것들이 무시될수 있습니다.

이를 위해서 선택할지 안할지에 대해서 경우를 나눠야 할것입니다.

하지만 단순히 경우를 나눠서 재귀를 돌리면 O(2^n)의 시간복잡도를 가지므로 비효율적입니다.

그래서 위 코드처럼보통은 DP(동적 계획법)을 사용해 상태 전이를 정의하고 중복 계산을 줄여 효율적으로 풉니다.


tenlemsp   1년 전

저 코드가 정확히 어떻게 돌아가는건지 모르겠어서 좀 더 읽어봐야겠지만..

아무튼 동적계획법을 써서 풀면 중복계산을 안해도 돼서 더 효율적이군요

알려주셔서 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.