01 Knapsack Problem
(dp/KnapsackProblem.hpp)

• View this file on GitHub
• Last update: 2025-09-30 00:05:33+09:00
• Include: #include "dp/KnapsackProblem.hpp"

概要

todo

計算量

todo

Verified with

• verify/AizuOnlineJudge/dp/DPL1_B.test.cpp

Code

template <class T>
vector<T> knapsack(const vector<int> &w, const vector<T> &v, const int W) {
    int n = int(v.size());
    T ng = numeric_limits<T>::min();
    vector<vector<T>> dp(n + 1, vector(W + 2, ng));
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= W; j++) {
            if (dp[i][j] == ng) continue;
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            dp[i + 1][min(j + w[i], W + 1)] = max(dp[i + 1][min(j + w[i], W + 1)], dp[i][j] + v[i]);
        }
    }
    return {dp[n].begin(), dp[n].end() - 1};
}

#line 1 "dp/KnapsackProblem.hpp"
template <class T>
vector<T> knapsack(const vector<int> &w, const vector<T> &v, const int W) {
    int n = int(v.size());
    T ng = numeric_limits<T>::min();
    vector<vector<T>> dp(n + 1, vector(W + 2, ng));
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= W; j++) {
            if (dp[i][j] == ng) continue;
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            dp[i + 1][min(j + w[i], W + 1)] = max(dp[i + 1][min(j + w[i], W + 1)], dp[i][j] + v[i]);
        }
    }
    return {dp[n].begin(), dp[n].end() - 1};
}

Back to top page