白駿1480号:宝石を集める
10267 ワード
宝石を集める
白駿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リリースマシンになっています.
Reference
この問題について(白駿1480号:宝石を集める), 我々は、より多くの情報をここで見つけました
https://velog.io/@ks1ksi/백준-1480번-보석-모으기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#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;
}
Reference
この問題について(白駿1480号:宝石を集める), 我々は、より多くの情報をここで見つけました https://velog.io/@ks1ksi/백준-1480번-보석-모으기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol