描述

已知一个背包最多能容纳物体的体积为V；
现有n个物品第i个物品的体积为v_i，第i个物品的重量为w；
求当前背包最多能装多大重量的物品？

方法一

思路

穷举法，递归
根据所给条件找出当前背包能装的最大重量的物品，由于每个物品只有一件，所以可以找出所有不超过背包体积的物品组合，从中选出重量最大的组合，该组合的重量即为当前背包最多能装的物品重量。
即对于一个物品存在装入背包与不装入背包两种情况：
1.当物品体积大于当前背包时，则该物品不放入背包；
2.当物品体积小于当前背包时，则分为放入背包和不放入被包两种组合。
通过暴力遍历找出物品所有的排列组合。
代码如下：

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        boolean[] flags = new boolean[n];
        int max = 0;
        for (int i = 0;i < n;++i){
            // 能够放入背包中
            if (vw[i][0] <= V){
                flags[i] = true;
                // 找出已经确定一个物品的组合的最大重量
                int temp = search(V-vw[i][0],n,vw,flags) + vw[i][1];
                // 取最大值
                max = Math.max(temp,max);
                flags[i] = false;
            }
        }
        return max;
    }
    // 遍历
    private int search(int V,int n,int[][] vw,boolean[] flags){
        int max = 0;
        for (int i = 0;i < n;++i){
            if (!flags[i] && vw[i][0] <= V){
                flags[i] = true;
                // 递归遍历
                int temp = search(V-vw[i][0],n,vw,flags) + vw[i][1];
                flags[i] = false;
                max = Math.max(temp,max);
            }
        }
        return max;
    }
}

时间复杂度： $O(n!)$ ，需要找出能够装下的物品的所有的组合，而对n个物品总共有n!种排列组合，所以最坏的情况下时间复杂度为 $O(n!)$ ；
空间复杂度： $O(n)$ ，使用布尔数组来记录物品是否已被装入背包，所以空间复杂度为 $O(n)$ 。

方法二

思路

动态规划；
方法一的时间复杂度过大导致程序运行超时，所以需要考虑降低算法的时间复杂度；
首先对于每个物品都只有两种选择放入背包和不放入背包，限制条件为物品体积需要小于背包体积，且背包中需要尽量装重量大的物品，故其存在如下子问题，将前i件物品放入容量为j的背包，所得到的最优价值f(i,j),如果，第i件物品不放，问题便转换成将前i-1件物品放入容量为j的背包的最佳组合，若第i件物品放入背包，则问题便为将前i-1件物品放入体积为j-V_i的背包中。
定义函数f(i,j)：表示当前背包剩余体积为j时，前i个物品最佳组合对应的重量，存在如下递推公式：

$f(i,j) = f(i-1,j)$ $j < V_i$
$f(i,j) = max\left\{f(i-1,j-v_i)+w_i,f(i-1,j)\right\}$ $j >= V_i$
创建二维dp数组，存储计算的中间结果，减少冗余计算。
举个栗子吧，假设背包体积为10，有四个物品其重量与体积为[[2,3],[4,3],[3,5],[7,5]]
1.首先当只有0个物品或者背包体积为0时

2.当只有一个物品时

3.当有两个物品时

4.最终结果如下：

最重为10
代码如下：

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        int[][] dp = new int[n+1][V+1];
        for (int i = 1;i < dp.length;++i){
            for(int j = 1;j <= V;++j){
               // 存放 i 号物品（前提是放得下这件物品）
               int valueWith_i = (j - vw[i-1][0] >= 0) ? 
                   (vw[i-1][1] + dp[i-1][j-vw[i-1][0]]) : 0;
               // 不存放 i 号物品
               int valueWithout_i = dp[i - 1][j];
               dp[i][j] = Math.max(valueWith_i, valueWithout_i);
            }
        }
        return dp[n][V];
    }
}

时间复杂度： $O(nv)$ ,双重循环，外层循环为n，内层循环尾V，所以时间复杂度为O(nv)；
空间复杂度： $O(nv)$ ，dp二维数组辅助运算。

题解 | #01背包#

描述

方法一

思路

方法二

思路