```
// 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
```
