背包问题

分类

首要，笔者将背包问题分成如下几类：

当然这并不包括全部的背包问题，只是以笔者预备面试、看面经及自己的亲身经历而言，熟练把握上图这几种背包问题不仅能快速入门，相信在面试手撕中遇到的背包问题也不会超出这个规模。

1. 0 1 背包

01背包的界说是有背包一个、物品若干，而且一个物品只能被挑选一次，问满意某某条件下的最大/最小。这种描述基本上便是背包问题了。背包问题的关键便是只能挑选一次，因而这儿先抛出结论，处理01背包时“外层遍历物品早年往后，内层遍历背包，从后往前”

这儿笔者又将01背包分成了“显着的”、和“需求转化的”，望文生义，显着的便是大白话告知你此题什么是背包什么是物品，像这种直接套模板就好了，而需求转化的往往看上去和背包毫无关系，但你又无从下手，这个时分要是能敏锐的发现它是个背包问题，标题就会变得很简单。

1-1 显着的背包问题

如题：

这种题型，显着的界说了什么是背包什么是物品。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[] vs = new int[N+1];
        int[] ws = new int[N+1];
        for(int i = 1;i <= N;i++){
            vs[i] = sc.nextInt();
            ws[i] = sc.nextInt();
        }
        int[] dp = new int[V+1];
        for(int i = 1;i <= N;i++){
            for(int j = V;j>=vs[i];j--){
                dp[j] = Math.max(dp[j],dp[j-vs[i]]+ws[i]);
            }
        }
        System.out.println(dp[V]);
    }
}

明显，此题便是给定物品若干，在满意某某条件的状况下往背包装，被问最值。明显的背包问题，直接套模板，外层遍历物品，将物品早年往后逐一测验，这是简单了解的，但为何里面遍历背包是从后往前呢，这儿无妨手推一下，假设一个物品分量为1，早年往后去测验这个物品的时分，内存早年往后遍历背包，那背包容积为1的时分能背的分量是dp[0] + 1 = 1，当遍历到2时同理变成了2，这就对立了，一个物品相当于被挑选了屡次，这儿只能挑选一次物品的话无论容量是1仍是2甚至1000，能背下的分量都是1罢了。因而遍历的次序是从后往前遍历背包。

1-2 需求转化的背包问题

此题的关键在于怎么将其转成背包问题，试想，当咱们有一个容积为总的石头分量的二分之一的一个背包，假设咱们能将其装满，那么所有的石头都会被相互砸碎，假设装不满，那么咱们就想尽办法将它装到尽可能的满，那么背包背住的最大值乘以2便是能砸碎的最大值！

因而，界说背包为dp[总分量二分之一]，价值和分量都为石头分量，故状况搬运方程dp[i] = max(dp[i],dp[i-stones[i]] + stones[i])。

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i = 0;i < stones.length;i++){
            sum += stones[i];
        }
        int target = (sum >> 1);
        int[] dp = new int[target + 1];
        for(int i = 0;i < stones.length;i++){
            for(int j = target;j >= stones[i];j--){
                dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] * 2;
    }

将问题转化成背包思维以后，套模板即可。
再试一个相似的：

首要假如零要加的数之和是left，要减的数的和是right，那么有如下等式成立：
left + right = sum；left – right = target；因而left = （sum + target）/2;
问题就变成了在nums中找若干个数，只能以加的形式组合成left的计划数。

状况表明dp[i] = x，便是用nums来表明出i的计划数是x

因而界说int dp[] = new int[left] ,dp[left]便是答案

初始化dp[0] = 1，也便是啥也没有得时分组成0得方法也有1种那便是啥也没有，这才干确保后边递推的时分有值。

确认遍历次序，外层从头遍历nums的值，内层从left开端遍历dp（为了防止重复使用）

状况搬运方程：dp[j] += dp[j – nums[i]]，能组成j – nums[i]的计划就肯定能组成j，由于当前的数便是nums[i]

    class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        if(nums.length == 1){
            if(target == nums[0] || target == -nums[0]){
                return 1;
            }
            return 0;
        }
        int sum = 0;
        for(int i = 0;i < nums.length;i++){
            sum += nums[i];
        }
        int left = (sum + target) >> 1;
        if((sum + target) % 2 != 0)return 0;
        int[] dp = new int[left + 1];
        dp[0] = 1;
        for(int i = 0;i < nums.length;i++){
            for(int j = left;j >= nums[i];j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
}

彻底背包

0，1背包的关键就在于一个物品只能挑选一次，因而在内嵌套循环中对背包进行遍历时需求从后往前进行遍历（如此便确保了一个物品只能被挑选一次）。在0，1背包中物品（标题中给的数组在外循环进行遍历），背包（依据题意设出的dp数组）在内循环进行遍历。彻底背包是给定了物品求满意某种条件下的最大计划数，这种是物品可以无限次进行挑选，与0，1背包相同，标题给定的数组为物品，而要求的东西可设为dp数组（背包），外循环相同对物品进行遍历而内循环则对背包早年往后进行遍历，如此的意图是为了将一个物品挑选无数次。

在彻底背包中又分为两种：

1、不考虑次序求计划数，也即是求组合数的问题，见下面例1，在这种状况物品只能被挑选一次（由于2，1与1，2只能算一种，因而只能挑选一次）此刻，为了确保物品只被挑选一次，因而外循环担任对物品进行遍历而内循环担任对背包进行遍历。

2、考虑次序求排列数的彻底背包，此种状况下1，2与2，1便要算两种，仍然在外层遍历物品的话就会导致1，2与2，1只能呈现一次（由于是按次序在外层只能遍历一次，因而1，2与2，1谁在前面就只能呈现谁）。关于这种状况下的彻底（物品可选n次）排列（不同的挑选次序导致不同计划）背包就需求在外层遍历背包而内层遍历物品，如此一来相当于内层循环会被遍历屡次，也便是1，2与2，1都会呈现到。见例2：

不考虑次序的彻底背包

该题是一种组合问题，也便是2，2，1和2，1，2当作一种，这种状况外层对物品进行遍历即可，不然上面这种就会被记作两种，内存对背包进行遍历时为了可以重复使用物品（彻底背包）则早年往后遍历而非从后往前。
总金额界说为背包dp[amount + 1]，dp[amount]便是计划数。
物品便是硬币集合。
状况搬运方程：dp[j] = dp[j – coins[i]] + dp[j];也便是能组成dp[j – coins[i]]的就一定能组成dp[j]。

    class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0;i < coins.length;i++){
            if(coins[i] > amount)continue;
            for(int j = coins[i];j <= amount;j++){
                dp[j] = dp[j - coins[i]] + dp[j];
            }
        }
        return dp[amount];
    }
}

考虑次序的彻底背包

这种类型的彻底背包问题和不考虑次序的区别就在于1，2，1这种算一种计划、1，1，2又算一种计划，假设仍是外层遍历物品就会导致这二种始终只能呈现一种，由于物品的添加次序已被固定。故总共外层遍历背包内层遍历物品，这样才干呈现不同的组合。

确认背包：dp[target + 1]，界说便是组成j的计划数；
状况搬运：dp[j] += dp[j-nums[i]] ;
遍历次序，外层背包，内层物品，早年往后：

    class Solution {
    public int combinationSum4(int[] nums, int target) {
        int dp[] = new int[target + 1];
        dp[0] = 1;
        for(int i = 1;i <= target;i++){
            for(int j = 0;j < nums.length;j++){
                if(i - nums[j] >= 0){
                    dp[i] += dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}

总结

读到这儿，基本的背包问题基本就熟悉了，但这并不是全部的背包问题，此文章仅仅针对手撕时的问题，手撕通常不会呈现极难的背包。把握这些标题再稍加练习即可。
最终总结：背包分为01背包和彻底背包，01背包又分为明显的和需求转化的，模板都是外层物品内层背包，背包早年往后。彻底背包又被分为不考虑次序的和考虑次序的，为了确保物品的屡次挑选，遍历次序都是早年往后，区别在于要考虑次序时外层遍历背包内层遍历物品，以确保呈现不同的次序。
完。