背包问题概述（Lintcode- 562.Backpack IV 问题解决）

[kaolalicai]

什么是背包问题

背包问题（ Knapsack problem ）是一种组合优化的NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

背包问题是动态规划算法的一个典型实例。动态规划是对解最优化问题的一种途径。它往往是针对一种最优化问题，根据问题的不同性质，确定不同的设计方法。详细可以查到往期文章进行回顾，这里主要围绕 Lintcode 平台中的一个算法编程问题展开讲解。

背包问题的类型

背包问题分为 0/1 背包，多重背包、完全背包这三大类:

0/1 背包问题描述：给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取 0 和 1.我们设物品 i 的装入状态为 xi,xi∈ (0,1)，此问题称为 0/1 背包问题。

例子：01 背包问题描述：有编号分别为 a,b,c,d,e 的五件物品，它们的重量分别是 2,2,6,5,4，它们的价值分别是 6,3,5,4,6，每件物品数量只有一个，现在给你个承重为 10 的背包，如何让背包里装入的物品具有最大的价值总和？

完全背包问题描述：有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 c，价值是 w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大？

例子：有编号分别为 a,b,c,d 的四件物品，它们的重量分别是 2,3,4,7，它们的价值分别是 1,3,5,9，每件物品数量无限个，现在给你个承重为 10 的背包，如何让背包里装入的物品具有最大的价值总和？

完全背包问题与 01 背包问题的区别在于每一件物品的数量都有无限个，而 01 背包每件物品数量只有一个。

多重背包问题描述：给定 N 种物品和一个容量为 C 的背包，第 i 种物品最多有 Mi 件可用，每件的重量是 Wi，价值是 Vi。问：将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大？

例子：多重背包问题描述：有编号分别为 a,b,c 的三件物品，它们的重量分别是 1，2，2，它们的价值分别是 6，10，20，他们的数目分别是 10，5，2，现在给你个承重为 8 的背包，如何让背包里装入的物品具有最大的价值总和？

多重背包和 01 背包、完全背包的区别：多重背包中每个物品的个数都是给定的，可能不是一个，绝对不是无限个。

下面简单分析完全背包的情况。

例子

给定一些物品数组和一个目标值，问有多少种可以组成目标的组合数，比如给定物品数组 [2,3,6,7] 和目标值 7, 那么就有 2 种可能：[7] 和 [2, 2, 3]。所以返回 2。

分析思路

不同于 01 背包问题的完全背包问题，完全背包问题强调了，每种物品都有无限件可以选取，那么我们最终要检查的状态就不在是 01 背包问题中的 O(VN)而是扩展成 O(VSUM(V/cost[i]))件物品，显然因为扩展了可能选择的情况，我们的时间复杂度激素飙升，在背包容量非常大，并且物品的耗费很小的时候，这种算法的时间复杂度显得力不从心。

我们来写一下大概思路：

1. 最后一步

   F[n][m]表示前 n个有 多少种方式拼出m

   最后一个选上：F[n][m] = Sum(F[n-1][m-A[ki]])

   最后一个不选上：F[n][m] = F[n-1][m]

2. 顺序从小到大

3. 边界情况

   F[k][0] = 1

代码实现

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    public int backPackIV(int[] nums, int target) {
        // write your code here
        int len = nums.length;
        if (len == 0) return 0;
        
        int[][] F = new int[len+1][target+1];
        
        
        for (int i = 0; i <= len; i++) {
            F[i][0] = 1;
        }
        
        for (int i = 1; i <= len; i++ ) {
            int item = nums[i-1];
            for (int k = 1; k <= target; k++) {
                F[i][k] = F[i-1][k];
                if (k >= item) {
                    F[i][k] += F[i][k - item];
                }
            }
        }
        
       
        return F[len][target];
    }
}

参考资料

1. 背包问题详解：01 背包、完全背包、多重背包
2. 背包问题九讲 02-完全背包问题总结

程序小哥介绍

考拉后端开发潮流少年White

颜值在线，衣品在线，系统开发以及维护在线。