01背包问题

jiezi

5 年前

有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 v[i]，价值是 w[i]。求解将哪些物品装入背包可使价值总和最大。

要么拿，要么不拿

dp 解决方法

关键就在于找到它的最优子问题，物品为 N 个，体积为 V，我们需要取二维状态的 dp

将前 i 个物品放入体积为 j 的背包中可以获得的最大价值->dp[i][j]

只有单件物品就只需要考虑放或者不放，如果放入，体积就需要减去 v[i]，价值就加上 w[i]

比如我们想要知道前 5 个物品放入体积为 9 的背包中最大价值是多少，物品 id 为 0 -4

也就是求 dp[4][9]， 需要知道dp[3][j],0<j<V, 然后再对物品 4 进行选取，根据 01 背包状态转移方程计算 dp4 最大价值；

要知道 dp[3][j], 我们就要知道dp[2][j], 再对物品 3 进行选取，根据 01 背包状态转移方程计算dp[3][j] 最大价值；

要知道 dp[2][j], 我们就要知道dp[1][j], 再对物品 3 进行选取，根据 01 背包状态转移方程计算dp[2][j] 最大价值；

要知道 dp[1][j], 我们就要知道dp[0][j], 再对物品 3 进行选取，根据 01 背包状态转移方程计算dp[0][j] 最大价值；

把 dp[i][0] 初始化为 0(0<=i<N)，体积为 0 最大价值为 0

计算流程

public int napzack01_first(int []w,int []v,int V,int N){int [][]dp = new int[N][V+1];
        for(int i=0;i<N;i++)
            for(int j=1;j<=V;j++)
                if(j>=v[i])
                    if(i==0) dp[0][j] = w[i];
                    else dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
                else
                    dp[i][j] = dp[i-1][j];
        return dp[N-1][V];
    }

第一次优化：二维数组优化为一维数组

我们可以从表格发现，当前行的数据只与上一行的数据有关，所以我们只要每次循环后确保数组保存了上一次计算的结果

问题以及解决：

我们从当前循环来看，计算体积为 5 的 dp 值最多只需要 0-4 的上一次计算的结果，如果顺序从小到大更新的话，我们计算 5 时，此时之前的 0-4 的值都被更新了，不是上一次计算的结果(而是当前计算的结果)，而后面的需要上一次前面的数据；所以我们不能从头开始，而应该从最后开始更新，从后往前，这样可以保证优先更新体积大的值而让体积小的值保留上一次就算的结果。

// 1 维 01 背包
    public int napzack01_second(int []w,int []v,int V,int N){int []dp = new int[V+1];
        for(int i=0;i<N;i++)
            for(int j=V;j>=0;j--)
                if(j>=v[i])
                    if(i==0) dp[j] = w[i];
                    else dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
        return dp[V];
    }

全部放满 01 背包：

我们之前讨论了一种是不要求全部放满的 01 背包，我们再看如果要求全部放满会有什么不同

如果我们把物品表换成这样：

如果我们想要全部放满，就拿不到物品 4，即使它价值 50，但是我们想要的是要把背包装满，这就涉及到初始化时的问题

我们需要为每一次循环放入物品到 j 的背包中设置一个能否放满的标志，每次判断这个标志来检查当前物品放入能否使得背包装满

我们只需要在初始化时把一维数组的 1-V 初始化为 -1，表示当前 0 个物品放入背包，不能装满这些体积的背包，把数组dp[0] 正常设置为 0，表示体积为 0 的背包可以被 0 个物品装满；然后我们在计算数组值时先判断 dp[j-v[i]] 是否为 -1，为 - 1 说明当前物品放入无法装满背包，则不进行修改数组的值；只有不为 - 1 才能继续放入，说明当前物品放入可以放满体积为 j 的背包

// 全部放满 01 背包
    public int napzack01_fourth(int []w,int []v,int V,int N){int []dp = new int[V+1];
        for(int i=0;i<dp.length;i++){dp[i] = -1;
        }
        dp[0] = 0;
        for(int i=0;i<N;i++)
            for(int j=V;j>=0;j--)
                if(j>=v[i]&&dp[j-v[i]]!=-1)
                    dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
        return dp[V];
    }

有 N 件物品（每个物品都有无限个）和一个容量为 V 的背包。第 i 件物品的费用是 v[i]，价值是 w[i]。求解将哪些物品（每个物品都可以装多个）装入背包可使价值总和最大。

优化前

我们每种物品最多有选取 V/v[i] 个，我们可以再多一次循环，计算选取 0-V/v[i] 个的最大价值

时间复杂度：每种物品有 V /v[i]个，共需要求解 N V 中状态，时间为 O（NVΣ(V/v[i])）

空间复杂度：O(N)

状态转移方程：

dp[j] = max{dp[j-1],dp[j-k*v[i]]+k*w[i]}

code

// 完全背包
    // 状态转移方程 dp[j] = dp[j-k*v[i]]+k*w[i]
    public int napzack_complete(int []w,int []v,int N,int V){int dp[] = new int [V+1];
        for(int i=0;i<N;i++)
            for(int j=0;j<=V;j++)
                for(int k=0;k*v[i]<=j;k++)
                    dp[j] = Math.max(dp[j-1],dp[j-k*v[i]]+k*w[i]);
        return dp[V];
    }

优化为 01 背包

我们记得在优化 01 背包时，我们为了获取到上一次计算的值，我们选择从后往前计算，但是完全背包 正好相反，这才是它此昂要的，完全背包因为需要累计多个同一物品的值，前一次计算可能是 1 个、2 个等等，下一次 j 变化了以后，计算的可能是 3 个或者更多，所以我们需要保存实时计算出来的多个同一物品的最大价值，我们选取从前往后的顺序，这样每次前面计算的我们都可以在 j 增大以后累加获得更多个同一物品的最大价值(根据状态转移方程可知，我们计算一个位置的最大价值只需要当前位置的上一次计算的值和当前次循环内更前面的值)

例如：

在我们计算第 2 个物品 dp[5]的时候，物品 2 的体积为 2，价值为 5，我们需要上一次计算也就是第一个物品的 dp[5]的值，还需要 dp[5-2]=dp[3]的值，dp[3]我们在本次循环内计算 dp[5]之前就已经算过了，dp[3]可能选了一个物品 2，也可能没有选，我们计算 dp[5]就根据这个 dp[3]的大小在进行选取，就可以进行多次选取。

根本上就是把一类物品转化为多个一种物品

我们不需要体积从 0 开始计算。而只需要在每个物品的循环内从当前物品的最小个数 1 开始，也就是v[i]（不需要 0 个是因为初始化的时候已经把体积为 0 的 dp 值设置为 0 了）

参数依然使用

code

// 把完全背包优化为 01 背包
    public int napzack_comlete01(int []w,int []v,int N,int V){int dp[] = new int[V+1];
        for(int i=0;i<N;i++)
            for(int j=v[i];j<=V;j++)
                dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
        return dp[V];
    }

01 背包问题

完全背包