7-J 평범한 배낭 질문 있습니다.

작성한 질문수 9

0

안녕하세요 윤교님 ㅎㅎ

같은 물건이 여러번 안담기고 재귀로 코드를 짤려면 어떤식으로 짜야 될까요??

>> 차원의 수를 늘리고 idx + 1을 하면서 점진적으로 하시면 됩니다. 한번 생각해보시구 시도해보시구 -> 제가 다듬은 코드 참고부탁드립니다.

제가 다듬은 코드는 다음과 같습니다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int n, k;
int w, v;
vector<pair<int, int>> vec;

int dp[100004][104];

int go(int weight, int idx) {
    if (idx == n || weight == 0) return 0;

    int& ret = dp[weight][idx];
    if (ret != -1) return ret;

    ret = go(weight, idx + 1);

    if (weight - vec[idx].first >= 0) {
        ret = max(ret, go(weight - vec[idx].first, idx + 1) + vec[idx].second);
    }

    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> w >> v;
        vec.push_back({ w, v });
    }
	fill(&dp[0][0], &dp[0][0] + 100004 * 104, -1); 

    cout << go(k, 0);
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.