01背包问题：

现有n个物品要装进背包,背包容量为m，第i件物品的重量为w[i],价值为v[i],选择价值最高方案。

解法：枚举i，j设前i个物品和背包容量为j时可以获得的最大价值

第i件物品：           装           不装

                      ↓            ↓

dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

dp[n][m]即为答案

for(int i = 1;i <= n;i++){
    for(int j = 0;j <= m;j++){
        if(j1][j];
        else dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
    }
}

完全背包问题：

现要装n个物品要进背包,背包容量为m，物品有n种，第i种物品的重量为w[i],价值为v[i],选择价值最高方案。

解法：枚举i，j设前i个物品和背包容量为j时可以获得的最大价值

第i件物品：  

dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i])

dp[n][m]即为答案

for(int i = 1;i <= n;i++){
    for(int j = 0;j <= m;j++){
        if(j1][j];
        else dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i])
    }
}

一维滚动法：

01背包：倒序循环

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

完全背包：正序循环

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

多重背包问题：现要装n个物品要进背包,背包容量为m，物品有n种，第i种物品的重量为w[i],价值为v[i]，最多可以选n[i]个,选择价值最高方案。

解法：对每个n[i]二进制拆分，作01背包。

n[i] = 2^k-1+d,其中d<2^k,拆成2⁰,2¹,2²,2³...2^k-1,d.

（一定能凑成<=n[i]的所有数字）

分组背包问题：现要装n个物品要进背包,背包容量为m，物品有n种，第i种物品的重量为w[i],价值为v[i]，每组背包最多选一个,选择价值最高方案。

解法：把所有的组当作一个物品,组内枚举选择哪个物品

囗囗囗囗囗囗-->囗

囗囗囗囗囗-->囗

囗囗囗囗-->囗

囗囗囗囗囗囗-->囗

二维！！！！！

第i组k件物品：w[i][k],v[i][k]即可

泛化物品

有一个函数h(x),分配给物品的费用a，得到的价值就是h(a),他就是泛化物品。

用k模拟物品分配体积

for(int i = 1;i <= n;i++){
    for(int j = m;j >= 0;j--){
        for(int k = 0;k <=j;k++){
            dp[i][j] = max(dp[i][j],dp[i-1][j-k]+v[i][k]);
        }
    }
}

01背包计数：n个物品，每个可选可不选，求体积不超过m下能拿走物品的方案数

0000000000000