今天学习了《背包》
背包分为01背包，无限背包，分组背包等等，一般来说背包问题是用动态规划实现的
常用来求解最优解、可行性、统计方案数等问题。
刚看到01背包时，还觉得不怎么难，可越到后面越不对劲，从二维数组变成了滚动数组，甚至最后还变成了一维数组，还分正序倒序，非常的繁琐
下面是01背包的代码
int dp[N][M];//考虑前 i 件物品，恰好放入容量为 j 的背包，获得的最大价值之和。
memset(dp,-0x3f3f3f3f,sizeof(dp)); //初始化为-INF，标记所有状态不可达
for (int i = 0; i <= n; i++) dp[i][0] = 0; //特判背包容量为 0
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (j < w[i]) //不能选
dp[i][j] = dp[i – 1][j];
else //不想选 选
dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – w[i]] + v[i]);
}
int ans = 0; //背包不一定装满，dp[n][m] 不一定是最优解，所以需要打擂！
for (int j = 0; j <= m; j++) ans = max(ans, dp[n][j]);
cout << ans << endl;