背包问题分类

主要掌握01背包和完全背包，参考下文：

01背包理论基础

背包问题的模版

先循环物品，再循环容量，01背包内层循环是从大到小，完全背包内层循环从小到大

//01背包
for (int i = 0; i < n; i++) {
    for (int j = m; j >= V[i]; j--) {
        f[j] = max(f[j], f[j-V[i]] + W[i]);
    }
}
//完全背包
for (int i = 0; i < n; i++) {
    for (int j = V[i]; j <= m; j++) {
        f[j] = max(f[j], f[j-V[i]] + W[i]);
    }
}

背包问题变体

分割等和子集