[白俊]こんにちは(1535)C++-完全探索,DP

https://www.acmicpc.net/problem/1535

質問する

勢俊は整形手術をした後、病院に入院しすぎた.入院中に自分のことを考えてくれた人に、勢俊が「ありがとう」と言う番だ.
勢俊のことを考えている人は全部でN人います.人の番号は1番からN番までです.势俊はi号の人に声をかけるとL[i]と同じ体力を失い、J[i]と同じ快楽を得る.勢俊はせいぜい一人一人に一度しか言えない.
勢俊の目標は与えられた体力の中で最大の喜びを感じることだ.勢俊の体力は100、快楽は0.勢俊の体力がゼロか負数なら、死後何の喜びも感じなかった.プログラムを書いて、世俊が得られる最大の楽しみを出力します.

にゅうしゅつりょく

[入力]
1行目はN人分(≦20).2行目は一人一人に声をかけるとき、失った体力は1番から順番に入り、3行目は一人一人に声をかけるとき、得た楽しみは1番から順番に入ります.体力と快楽は100の自然数または0以下である.
[出力]
第1行は勢俊が得ることができる最大の楽しみを出力します.

🧐解き方

徹底した探索で問題を解決した.このインデックスを포함하는 경우と포함하지 않는 경우に分けて探索し,体力が0であれば戻るように編成すればよい.

solve(idx+1,strong-strength[idx], pleasure + happy[idx]);
solve(idx+1,strong, pleasure);

完全なコード

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

using namespace std;
//체력은 100, 기쁨은 0 -> 최대 기쁨을 출력
int n;
vector<int> strength;
vector<int> happy;

int max_pleasure = 0;

void solve(int idx, int strong, int pleasure) {
    
    if(strong <= 0 || idx >= n) {
        if(max_pleasure < pleasure) {
            max_pleasure = pleasure;
        }
        return;
    }
    
    //포함하는 경우, 포함하지 않는 경우
    solve(idx+1,strong-strength[idx], pleasure + happy[idx]);
    solve(idx+1,strong, pleasure);
}

int main() {
    cin >> n;
    
    for(int i =0; i < n; i++) {
        int x;
        cin >> x;
        strength.push_back(x);
    }
    
    for(int i =0; i < n; i++) {
        int x;
        cin >> x;
        happy.push_back(x);
    }
    solve(0,100,0);
    
    cout << max_pleasure << endl;
    
}

検索してみると、DPで問題を解決する場合もあります.DPを使用すると、より少ない時間がかかる場合があります.

DPコード

int n, strong[21], pleasure[21], dp[101];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	for (int i = 0; i <n; i++) {
		for (int j = 100; j >= strong[i]; j--) {
			dp[j] = max(dp[j], dp[j - strong[i]] + pleasure[i]);
		}
	}

	cout << dp[99];

}

👉 現在保存されているインデックスに同様に含まれるか含まないかで、最大の状況をdpに保存すればよい.