エンジニアとしての市場価値を測りませんか?PR

企業からあなたに合ったオリジナルのスカウトを受け取って、市場価値を測りましょう

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

ナップサック問題

Last updated at Posted at 2022-03-14

問題 dpイメージ

dp[i][w] :
i 番目までの品物の中から (選ぶ、選ばない 選択)
重さが w を超えないように選んだときの、
価値の総和の最大値

// 入力
ll n, W; //荷物の数、許容容量
ll weight[110], value[110]; //重さ、価値

ll dp[110][10010]; //個数、重さ

int main() {
    cin >> n >> W;
    for (ll i = 0; i < n; ++i) cin >> value[i] >> weight[i];

    // DP初期条件: dp[0][w] = 0
    for (ll w = 0; w <= W; ++w) dp[0][w] = 0;

    // DPループ
    for (ll i = 0; i <= n; ++i) { //荷物の数
        for (ll w = 0; w <= W; ++w) { //許容容量
            if (w >= weight[i]) dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w]);
            else dp[i + 1][w] = dp[i][w]; //最初のみ使用
        }
    }

    cout << dp[n][W] << endl; //n以下 W以下 の最大値
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up

Qiita Advent Calendar is held!

Qiita Advent Calendar is an article posting event where you post articles by filling a calendar 🎅

Some calendars come with gifts and some gifts are drawn from all calendars 👀

Please tie the article to your calendar and let's enjoy Christmas together!

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?