[競プロ][C++] Knapsack DP

背景
投稿者投稿者Demystify  いいね1  お気に入り登録
プレイ回数329  難易度(3.4) 444打 英語 記号
タグ競プロ C++
[2022/7/30] 「i+1 -> i + 1」のような変更をしました。

関連タイピング

関連タイピング一覧

問題文

ふりがな非表示 ふりがな表示

(#include <bits/stdc++.h>)

#include <bits/stdc++.h>

(using namespace std;)

using namespace std;

(int main() {)

int main() {

(int N, W;)

int N, W;

(cin >> N >> W;)

cin >> N >> W;

(vector<int> w(N), v(N);)

vector<int> w(N), v(N);

(for (int i = 0; i < N; i++) {)

for (int i = 0; i < N; i++) {

(cin >> w[i] >> v[i];)

cin >> w[i] >> v[i];

(})

}

(vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));)

vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));

(for (int i = 0; i < N; i++) {)

for (int i = 0; i < N; i++) {

(for (int j = 0; j <= W; j++) {)

for (int j = 0; j <= W; j++) {

(if (0 <= j - w[i]) {)

if (0 <= j - w[i]) {

(dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);)

dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);

(} else {)

} else {

(dp[i + 1][j] = dp[i][j];)

dp[i + 1][j] = dp[i][j];

(})

}

(})

}

(})

}

(int ans = *max_element(dp[N].begin(), dp[N].end());)

int ans = *max_element(dp[N].begin(), dp[N].end());

など

(cout << ans << endl;)

cout << ans << endl;

(})

}

問題文を全て表示 一部のみ表示 誤字・脱字等の報告