Language: C++

/**
 * @brief  0-1ナップサック問題(0-1 knapsack problem)は次の問題である
 *
 *         泥棒がある店に盗みに入ってn個の品物を見つけた. i番目の品物はviドルの価値があり、重さはwiポンドである
 *         ただし、viとwiは整数である. 彼はできるだけ高価な品物を盗りたいが、彼のナップサックでは高々Wポンド(Wは整数)の荷物しか運べない
 *
 *         各品物は盗るか残すかのどちらかなので、この問題は0-1ナップサック問題と呼ばれる
 *         この泥棒は品物の一部だけを盗ったり、同じものを複数回盗ることはできない
 *
 * @note   n個の各品物について、「盗る」か「残す」かの組み合わせをすべて調べるアルゴリズムの計算効率はΟ(2^n)となってしまい、　
 *         大きな入力nに対して解くことができないが、品物の大きさw, ナップサックの大きさWがともに整数であれば、
 *         0-1ナップサック問題は動的計画法によりΟ(nW)の計算効率で厳密解を求めることができる
 *
 * @note   次のような変数を用意する
 *
 *           v[n+1]       i番目の品物の価値が記録されている1次元配列
 *           w[n+1]       i番目の品物の重さが記録されている1次元配列
 *           C[n+1][W+1]  i個目までの品物を考慮して大きさjのナップサックに入れる場合の価値の合計の最大値をC[i][j]とする2次元配列
 *
 *         考慮する品物の数i, 各iにおけるナップサックの重さjを増やしていき、C[i][j]を変更していく. C[i][j]の値は、
 *
 *           1. C[i - 1][j - 品物iの重さ] + 品物iの価値
 *           2. C[i - 1][j]
 *
 *         の大きい方となる. ここで1.はこの時点で品物iを盗る、2.はこの時点で品物iを残す、という処理に対応する
 *         ただし、1.の場合は、品物iの重さがjを超えない場合に限る
 *
 * @date   2016/05/05
 */



//********************************************************************************
// 必要なヘッダファイルのインクルード
//********************************************************************************

#include <iostream>
#include <vector>
#include <cstdint>



//********************************************************************************
// 型シノニム
//********************************************************************************

using index_t  = std::int_fast32_t;
using value_t  = std::int_fast32_t;
using weight_t = std::int_fast32_t;

using indices_t = std::vector<index_t>;
using values_t  = std::vector<value_t>;
using weights_t = std::vector<weight_t>;

using dptbl_t   = std::vector<values_t>;



//********************************************************************************
// 大域変数の定義
//********************************************************************************

static const value_t INF = std::numeric_limits<value_t>::max() / 3;



//********************************************************************************
// 関数の定義
//********************************************************************************

/**
 * @brief  動的計画法を用いて0-1ナップサック問題(0-1 knapsack problem)を解きます
 *
 * @param  const value_t& v i番目の品物の価値が記録されている1次元配列v
 * @param  const value_t& w i番目の品物の重さが記録されている1次元配列w
 * @param  weight_t       W ナップサックに詰めこめる最大の重さW
 */
value_t __01_knapsack__(const values_t& v, const weights_t& w, weight_t W)
{    
    index_t n = v.size();                // n = v.length
    dptbl_t C(n+1, values_t(W+1, INF));  // Cを(n+1) x (W+1)型の新しい行列とする
    
    for (index_t  i = 0; i <= n; i++) { C[i][0] = 0; }
    for (weight_t j = 0; j <= W; j++) { C[0][j] = 0; } 

    for (index_t i = 1; i <= n; i++) {

        for (weight_t j = 1; j <= W; j++) {

            if (w[i] <= j) {
                C[i][j] = std::max(C[i - 1][j - w[i]] + v[i], C[i - 1][j]);
            }
            else {
                C[i][j] = C[i - 1][j];
            }
        }
    }
    
    return C[n][W];
}



//********************************************************************************
// エントリポイント
//********************************************************************************

int main()
{
    using namespace std;

    int n, W;
    cin >> n >> W;
    
    values_t  v(n);
    weights_t w(n);

    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    cout << __01_knapsack__(v, w, W) << endl;
    
    return 0;
}

Compiler output:
a.cc:63:33: error: 'numeric_limits' is not a member of 'std'
   63 | static const value_t INF = std::numeric_limits<value_t>::max() / 3;
      |                                 ^~~~~~~~~~~~~~
a.cc:63:55: error: expected primary-expression before '>' token
   63 | static const value_t INF = std::numeric_limits<value_t>::max() / 3;
      |                                                       ^
a.cc:63:58: error: '::max' has not been declared; did you mean 'std::max'?
   63 | static const value_t INF = std::numeric_limits<value_t>::max() / 3;
      |                                                          ^~~
      |                                                          std::max
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:37:
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: 'std::max' declared here
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~