01背包:n种物品,你的背包容量m,每种物品最多取一次,求最大的价值 完全背包:同01,不过,每种物品可以拿无限次 多重背包:就是在原本的背包基础上,对每种物品的个数进行限制。 即:给出物品的重量、价值以及个数。 统一解释:w[i]表示i物品的重量(体积) v[i]表示i物品的价值 01背包 我们直接对于所有物品遍历,再遍历所有的剩余容量递推即可。 #include #include using namespace std; const int maxn = 1e3 + 50; int w[maxn]; int v[maxn]; int dp[maxn] = {0}