题目描述

01背包 vs 完全背包 vs 多重背包的理解总结.

样例

01背包未维度优化. 
        for(int i=1;i<=n; i++){
            for(int j=0; j<=m; j++){

                f[i][j] = f[i-1][j];
                if(j >= v[i]){
                    f[i][j] = Math.max(f[i][j], f[i-1][j-v[i]] + w[i]);
                }
            }
        }

    }
}

完全背包未维度优化
        for(int i=1; i<=n;i++){
            for(int j = 0;j<=m; j++){
                //朴素算法 
                // f[i][j] = Math.max(f[i-1][j-v[i]*k] + w[i]*k, f[i][j]);
                f[i][j] = f[i-1][j];
                if(j>= v[i]){
                    f[i][j] = Math.max(f[i][j], f[i][j-v[i]] + w[i]);
                }
            }
        }

区别

01背包 f[i][j] = Math.max(f[i][j], f[i-1][j-v[i]] + w[i]);
完全背包 f[i][j] = Math.max(f[i][j], f[i][j-v[i]] + w[i]);

01 更新状态时,用的未包含当前i的 表达式为： f [i-1][j-v[i]]
完全背包更新, 用的包含当前i 表达式为： f[i][j-v[i]]

维度优化后
        for(int i=1;i<=n; i++){
            //for(int j = v[i];j<=m; j++){ //完全背包
            for(int j=m; j>=v[i]; j--){// 01背包
                f[j] = Math.max(f[j],f[j-v[i]] + w[i]);
            }
        }

维度优化后区别

01 背包 ：容量从大到小 计算
完全背包：容量从小到大 计算

小到大时,当前 j 更新过了, 可理解为i 行的j
大到小时,当前 j 未更新过, 可理解为i-1 行的 j

多重背包

思路：
用二进制法拆分 则可是log(n)上取整的复杂度.
从大到小拆分限定的个数.
最后成为01 背包问题.

多重背包 III

for(int i=0; i<n; i++){
    for(int j=0; j<=m; j){
        f[i][j] = f[i-1][j];
        for(int k=1; k<=si&&k*vi<=j; k){
            f[i][j] = Math.max(f[i][j], f[i-1][j-kvi]+kwi);
        }
    }
}

思路：

转移方程 ： f[i][j] = Math.max(f[i][j], f[i-1][j-kvi]+kwi);

当前物品体积 vi, 枚举每一个体积j下的max,

!! 每次更新 均是来自 j-k*vi 中,
!! 意味着： j mod vi 模值相同的j中 各个模值对应的v的集合都是相互独立的,不互相影响的.

例: j = 15, vi = 3 则可以将j 分为三组
{1， 4， 7， 10， 13}
{2， 5， 8， 11， 14}
{3， 6， 9， 12， 15}

f[i-1][j]更新 只从j % vi ~ j 中的!价值最大!
按组更新， 不用 每个j都从头找最大值了

一组的公式为：
f[j] = f[j-v] + w, f[j-2v] + 2w… f[j-kv] + kw;
此时每组 满足单调队列条件,
又因为公式为等差数列, 我们求的是最大值,
每次
f[0]
f[v] - 1 * w
f[2v] - 2 * w

import java.util.*;
import java.io.*;

class Main{

    static int N = 1010;
    //f,g,q 分别存储 g = f[i][j]， g = f[i-1][j],  q = 单调队列
    static int[] f, g, q;
    public static void main(String[] args) throws Exception{
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); //物品个数
        int m = in.nextInt(); //总体积
        f = new int[m+10];
        g = new int[m+10];
        q = new int[m+10];

        int vi, wi, si;

        for(int i=1; i<= n; i++){
            vi = in.nextInt(); // 当前物品体积
            wi = in.nextInt(); // 当前物品价值
            si = in.nextInt(); // 当前物品数量

            for(int j=0; j<vi; j++){  // 因为是% vi分组 所以所有j 都< vi;

                //单调队列头尾
                int hh = 0 , tt = -1;

                for(int k = j; k<=m; k+=vi){
                    g[k] = f[k]; //保留f[i-1][j] , f[k]随时可能更新. 

                    // 单调队列- 队头存最大元素. 
                    if(hh<=tt && k-q[hh])/vi > si) hh++; //窗口大小为si
                    // g[队尾] + (当前k - q最大价值的体积)/vi * wi
                    // 意思为 当前k队尾最大价值 < 当前最大价值. 则队尾出队. 
                    while(hh<=tt && g[q[tt]] < f[k] - (k-q[tt])/vi*wi ) tt--;
                    q[++tt] = k;

                    // f[k] = 当前价值最大的 k
                    f[k] = g[q[hh]] + (k-q[hh]) / vi * wi;
                }

            }
        }

        System.out.println(f[m]);
    }
}