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 i, int weight) {
    int res = 0;
    if (memo.find(make_pair(i, weight)) != memo.end()) {
        return memo[make_pair(i, weight)];
    }
    // 商品なし
    if (i == v_list.size()) {
        res = 0;
    }
    // 商品が選べない
    else if (weight < w_list[i]) {
        res = knapsack(i + 1, weight);
    }
    else {
        // 商品を選ぶ場合と，選ばない場合でいい方
        res = max(knapsack(i + 1, weight), knapsack(i + 1, weight - w_list[i]) + v_list[i]);
    }
    return memo[make_pair(i, weight)] = res;

}
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(0, W) << endl;
    return 0;
}