背包DP是个好东西，它可以模拟一个背包，看重量装东西，最后看东西的总价值最大。这就是他的基础能力

(注释:此博客中V代表背包容量，n代表物品数量，w[i]表示第i种物品的体积，c[i]表示第i种物品的价值，后面不多加解释)

先讲01背包

众所众之，DP题目有五步：

1.能不能用

背包一眼就能看出，无法回头，子问题重叠，有最优子结构

2.定义状态变量

f[n][v]

3.状态转移方程

f[i][j]=f[i-1][j];//不选
f[i][j]=max(f[i-1][j-w[i]]+c[i]);//选

4.初始化和边界值

f[i][j]=0;

5.找答案

cout<<f[n][v];

---

接下来是01背包的模板

for(int i=1;i<=n;i++){
    for(int j=v;j>=w[i];j--){
        f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
    }
}

对了，其实一维数组也可以写背包

当然，背包除了这些还有很多变种

---

例如：

肥肠重要的多重背包，就是给每件物品增加了数量

我这里把数量存放在sum数组中

代码如下

for(int i=1;i<=n;i++){
    for(int j=v;j>=0;j--){
        for(int k=0;k<=sum[i];k++){//枚举数量
            if(j>=k*w[i])f[i][j]=max(f[i-1][j],f[i-1][j-w[i]*k]+c[i]*k);
        }
    }
}

---