宝石を集める

白駿1480号:宝石を集める

アイデア

現在のリュックの番号、現在のリュックの中の宝石の重さ、これまでの宝石リストの注釈は今から始まります
装着された宝石や、宝石の重量がリュックサックの重量より大きい場合は探索しません.宝石の重さはバッグの重さより軽いのですが、現在バッグの中に別の宝石が入っていて、宝石を入れられない場合は、次のバッグに渡します.このとき最後のバッグをひっくり返すと-1を返して数字を合わせるのがポイントです

コード#コード#

#include <bits/stdc++.h>

using namespace std;

int N, M, C; // gem, bag, limit
int arr[13];
int cache[11][21][1<<13]; // bag, weight, visited

int solve(int bag, int weight, int visited) {
    if (bag == M) return -1;
    if (visited == (1<<N)-1) return 0;

    int& ret = cache[bag][weight][visited];
    if (ret != -1) return ret;

    ret = 0;
    for (int i = 0; i < N; i++) {
        if (visited&(1<<i)) continue;
        else if (arr[i] > C) continue;
        else if (weight+arr[i] > C) {
            ret = max(ret, solve(bag+1, arr[i], visited|(1<<i))+1);
        }
        else {
            ret = max(ret, solve(bag, weight+arr[i], visited|(1<<i))+1);
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> C;
    for (int i = 0 ; i < N; i++) {
        cin >> arr[i];
    }
    memset(cache, -1, sizeof(cache));
    cout << solve(0, 0, 0);
    return 0;
}

おしゃべり

ビットマスクDPリリースマシンになっています.