7-x_1480 질문 있습니다

안녕하세요 02님 ㅎㅎ

if(!isbeforeYAM && isYAMCAN)ret = max(ret, go(here, yamyam | (1 << i), capacity - a[i]) + 1);

제 코드를 보시면 sort를 하고 넣는게 아닙니다. 하나하나 넣어가며 모든 경우의 수를 다 파악합니다.

근데 02님 코드를 보시면 dp 배열 여러개를 만들고 각 배열마다 최적해를 담아서 해당 cnt를 +하는 것인데요.

그방식 자체가 이 명제 기반으로 하는 건데요.

지금 넣을 보석의 개수가 기존에 넣었던 보석의 개수 보다 많으면 갱신

흠.. 이부분 괜찮은 거 같아서 저도 몇번 시도해봤는데 뭔가 반례가 있는 것 같네요.

저는 02님 코드를 좀 더 단순하게 만들어봤는데요.

#include <bits/stdc++.h>
using namespace std;

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

    int n, m, c;
    cin >> n >> m >> c;

    vector<int> jewels(n);
    for (int i = 0; i < n; ++i) {
        cin >> jewels[i];
    }

    int cnt = 0;
    vector<bool> taken(n, false);

    for (int bag = 0; bag < m; ++bag) {
        vector<vector<int>> dp(c + 1);
        for (int i = 0; i < n; ++i) {
            if (!taken[i]) {
                for (int weight = c; weight >= jewels[i]; --weight) {
                    if (dp[weight - jewels[i]].size() + 1 > dp[weight].size()) {
                        dp[weight] = dp[weight - jewels[i]];
                        dp[weight].push_back(i);
                    }
                }
            }
        }

        cnt += dp[c].size();
        for (int idx : dp[c]) {
            taken[idx] = true;
        }
    }

    cout << cnt << '\n';
    return 0;
}

틀립니다.

뭔가 반례가 있는 것 같은데.. 찾기가 쉽지 않네요.

모든 경우의 수를 찾는 방식으로 바꿔야 할 것 같습니다.

부족한 답변 죄송합니다. ㅠㅠ..

감사합니다.

인프런 커뮤니티 질문&답변