knapsack.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<int> v_list;
vector<int> w_list;
map<pair<int, int>, int> memo;

int knapsack(int w) {
    vector<vector<int>> dp(v_list.size() + 1, vector<int>(w + 1, 0));

    for (int i = 0; i < v_list.size(); ++i) {
        for (int j = 0; j < w + 1; ++j) {
            if (j + w_list[i] <= w) {
                dp[i + 1][j + w_list[i]] = dp[i][j] + v_list[i];    // 品物をとる
            }
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);             // 品物をとらない
        }
    }

    return dp[dp.size() - 1][w];
}

int main(int argc, char *argv[]) {
    v_list = {4, 4, 5, 2, 8};
    w_list = {5, 2, 2, 1, 3};
    int W = 5;
    cout << knapsack(W) << endl;
    return 0;
}