关于程序员:数据结构与算法动态规划学习笔记背包问题

「数据结构与算法」动静布局学习笔记：背包问题

定义

给定一个背包容量 target ，再给定一个数组 nums(物品) ，是否按肯定形式选取 nums 中的元素失去 target

留神：

背包容量target和物品nums的类型可能是数，也可能是字符串
target可能题目曾经给出（显式），也可能是须要咱们从题目的信息中开掘进去（非显式）（常见的非显式target比方sum/2等）
选取形式有常见的一下几种：每个元素选一次/每个元素选屡次/选元素进行排列组合

模板

二维

// 0-1背包问题母代码(二维)private int bags() {    // 各个物品的分量    int[] weight = new int[] {1, 3, 4};    // 对应的价值    int[] value = new int[] {15, 20, 30};    // 背包最大能放下多重的物品    int bagSize = 4;    // 二维数组：状态定义:dp[i][j]示意从0-i个物品中抉择不超过j分量的物品的最大价值    int[][] dp = new int[weight.length][bagSize + 1];    // 初始化:第一列都是0，第一行示意只选取0号物品最大价值    for (int j = bagSize; j >= weight[0]; j--) {        dp[0][j] = dp[0][j - weight[0]] + value[0];    }    for (int i = 1; i < weight.size(); i++) {        // 遍历物品(第0个物品曾经初始化)        for (int j = 0; j <= bagSize; j++) {            // 遍历背包容量            if (j < weight[i]) {                // 背包容量曾经不足以拿第i个物品了                // 最大价值就是拿第i-1个物品的最大价值                dp[i][j] = dp[i - 1][j];            } else {                // 背包容量足够拿第i个物品，可拿可不拿：                // 拿了最大价值是前i-1个物品扣除第i个物品的分量的最大价值，加上i个物品的价值                // 不拿就是前i-1个物品的最大价值                // 两者进行比拟取较大的                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);            }        }    }    return dp[weight.size - 1][bagSize];}

二维优化至一维

// 0-1背包问题母代码(一维)private int bags() {    // 各个物品的分量    int[] weight = new int[] {1, 3, 4};    // 对应的价值    int[] value = new int[] {15, 20, 30};    // 背包最大能放下多重的物品    int bagSize = 4;    // 一维数组：状态定义:dp[i]示意抉择不超过i分量的物品的最大价值    int[] dp = new int[bagSize + 1];    for (int i = 0; i < weight.size(); i++) {        // 遍历物品        for (int j = bagSize; j >= weight[i]; j--) {            // 遍历背包容量（肯定要逆序）            // 不取或者取第i个            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);        }    }    return dp[bagSize];}

分类模板

背包问题大体的解题模板是两层循环，别离遍历物品 nums 和背包容量 target ，而后写转移方程。
依据背包的分类咱们确定物品和容量遍历的先后顺序，依据问题的分类咱们确定状态转移方程的写法

首先是背包分类的模板：

0/1背包：外循环 nums ，内循环 target ， target 倒序且 target>=nums[i]
齐全背包：外循环 nums ，内循环 target ， target 正序且 target>=nums[i]
组合背包：外循环 target ，内循环 nums ， target 正序且 target>=nums[i]
分组背包：这个比拟非凡，须要三重循环：外循环背包bags，外部两层循环依据题目的要求转化为1、2、3三种背包类型的模板

而后是问题分类的模板：

最值问题： dp[i] = max/min(dp[i], dp[i-nums]+1) 或 dp[i] = max/min(dp[i], dp[i-num]+nums)
存在问题： dp[i] = dp[i]||dp[i-num]
组合问题： dp[i] += dp[i-num]

「数据结构与算法」动静布局学习笔记：背包问题

定义

分类：

模板

分类模板