01 背包问题
当前有 N 件物品和一个容积为 V 的背包。已知第 i 件物品的体积是 ci，价值是 wi。
由于每种物品 有且仅有一件，并且 体积不可分割，因此只能选择放或不放，我们称之为 01 背包问题。
现在需要选出若干件物品，在它们的体积之和不超过 V 的条件下，使得价值总和尽可能大。
对于每个物品是否要装入背包，我们自然可以进行暴力枚举或搜索，但是如果要暴力地去做，那么时间复杂度会非常的高，这时候需要一种更优的算法——动态规划。
对于 01 背包，先确定这个问题的状态。
共有 N 个物品，背包总容量为 V，那么可以根据物品和容量来确定一个状态。
前 i 个物品，放在背包里，体积之和不超过 j 的前提下，所获得的最大价值为 dp[i][j]。
是否将第 i 个物品装入背包中，就是决策。
当容量小于第 i 个物品的体积时，我们无法将其放入背包。
为了使价值最大化，如果第 i 个物品放入背包后，总体积不超过限制且总价值比之前要大，那么就将第 i 个物品放入背包。
根据这个逻辑写出转移方程：
当 j<ci 时， dp[i][j]=dp[i−1][j]
当 ci≤j≤V 时， dp[i][j]=max(dp[i−1][j],dp[i−1][j−ci]+wi)
核心代码:
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= V; ++j) {
if(j >= c[i]) {
dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}时间上是两重循环，时间复杂度为O(NV)。
空间是二维的，空间复杂度也为O(NV)。
完整代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[21][1010];
int w[21], c[21];
int main() {
int N, V;
cin >> N >> V;
for (int i = 1; i <= N; i++) {
cin >> w[i] >> c[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if (j >= c[i]) {
dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[N][V] << endl;
return 0;
}