```
// 01knapsackProblem210801.cpp : 此文件包含 "main" 函數。程序執行將在此處開始并結束。//
#include <iostream>
#include<cstring>
using namespace std;
const int MAX_N = 100;
//輸入
int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N + 1][MAX_N + 1];//記憶化數組
//從第i個物品開始挑選重量小于j的部分
int rec(int i, int j)
{
if (dp[i][j] >= 0)
{//已經計算過的話直接使用之前的結果
return dp[i][j];
}
int res;
if (i == n)
{//已經沒有剩余物品了
res = 0;
}
else if (j < w[i])
{//無法挑選這個物品
res = rec(i + 1, j);
}
else
{//挑選和不挑選的兩種情況都嘗試一下
res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
}
return dp[i][j] = res;
}
int main()
{
cout << "[n:";
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "["; cout << i;
cout << "(w(";
cin >> w[i];
cout << "v(";
cin>> v[i];
}
cout << "W";
cin >> W;
//用-1表示未計算過，初始化整個數組
memset(dp, -1, sizeof(dp));//使用memset快速對高維數組進行初始化
cout << rec(0, W) << endl;
return 0;
}// 01背包問題
//https://cloud.tencent.com/developer/article/1747146
```
