一、01背包问题详解
- 确定dp数组以及下标的含义
dp[ i ] [ j ] 表示前 i 件物品放入一个容量为 j 的背包可以获得的最大价值（每件物品最多放一次）
- 确定递推公式
-
dp数组的初始化
首先从dp[i][j] 的定义出发，如果背包容量j为0的话，即dp [i] [0] ，无论是选取哪些物品，背包价值总和一定为0。如图：
-
状态转移方程 dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。 dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
- 那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
- 当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
function testWeightBagProblem (weight, value, size) {
const dp = Array(weight.length).fill().map(() => Array(size + 1).fill(0));
for(let j = weight[0]; j size; j++) {
dp[0][j] = value[0];
}
for(let i = 1; i < weight.length; i++) {
for(let j = 0; j size; j++) {
if(j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
return dp[len - 1][size];
}
function test () {
console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}
test();
下面两个题目里的数组都是代表物品的重量，不涉及物品的价值。
416. 分割等和子集
var canPartition = function(nums) {
let n = nums.length
let sum = 0
for(const s of nums){
sum += s
}
if(sum % 2 != 0) return false
const targetSum = sum / 2
if(Math.max(...nums) > targetSum) return false
let dp = new Array(n+1).fill().map(() => new Array(targetSum+1).fill(false))
dp[0][0] = true
for(let i = 1; i n; i++) {
for(let j = 0; j targetSum; j++) {
if(j < nums[i-1]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i-1]];
}
}
return dp[n][targetSum]
};
494. 目标和
题目链接
假设所有符号为+的元素和为x，符号为-的元素和的绝对值是y。
- 我们想要的 S = 正数和 – 负数和 = x – y
- 已知x与y的和是数组总和：x + y = sum
- 可以求出 x = (S + sum) / 2 = target，问题为从nums数组里选出几个数，令其和为target。
比如nums = [1,1,1,1,1], target = 3。-1 + 1 + 1 + 1 + 1 = 3 中所有符号为+的元素为4，-的元素的1。所以正数和4 – 负数和1 = 3.
var findTargetSumWays = function(nums, target) {
let sum = 0
for (const s of nums){
sum += s
}
const diff = sum - target;
if (diff < 0 || diff % 2 !== 0) {
return 0;
}
const n = nums.length, neg = diff / 2;
const dp = new Array(n + 1).fill(0).map(() => new Array(neg + 1).fill(0));
dp[0][0] = 1
for(let i=1; in; i++){
for(let j=0; jneg; j++){
if(j < nums[i-1]){
dp[i][j] = dp[i-1][j]
}else{
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
}
}
}
return dp[n][neg]
};
二、完全背包
; 322. 零钱兑换
题目链接
详解
这个题目和上面的两个01背包问题不一样，这个是涉及物品的价值的问题。物品的价值就是硬币的数量。初始化就是考虑dp[0][0] , dp[0][j], dp[i][0] 这三种情况。
var coinChange = function(coins, amount) {
const n = coins.length
const dp = new Array(n+1).fill().map(() => new Array(amount+1).fill(Infinity))
dp[0][0] = 0
for(let i=1; in; i++){
for(let j=0; jamount; j++){
if(j < coins[i-1]){
dp[i][j] = dp[i-1][j]
}else{
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i-1]] + 1)
}
}
}
return dp[n][amount] == Infinity ? -1 : dp[n][amount]
};
518. 零钱兑换 II
上个题目是硬币数的最小值，这个题目不涉及物品的价值，就是单纯的组合。所以进行稍微的改动即可。
var change = function(amount, coins) {
const n = coins.length
const dp = new Array(n+1).fill().map(() => new Array(amount+1).fill(0))
dp[0][0] = 1
for(let i=1; in; i++){
for(let j=0; jamount; j++){
if(j < coins[i-1]){
dp[i][j] = dp[i-1][j]
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
}
}
}
return dp[n][amount]
};
279. 完全平方数
var numSquares = function(n) {
let nums=[], i=1;
while(i*i n){
nums.push(i*i)
i++
}
let len = nums.length, cap = n;
const dp = new Array(len+1).fill().map(() => new Array(cap+1).fill(Infinity))
dp[0][0] = 0
for(let i=1; ilen; i++){
for(let j=0; jcap; j++){
if(j < nums[i-1]){
dp[i][j] = dp[i-1][j]
}else{
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-nums[i-1]] + 1)
}
}
}
return dp[len][cap]
};
Original: https://blog.csdn.net/weixin_43466639/article/details/128327788
Author: 是馨呀！
Title: 01背包问题以及有关题目
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/721945/
转载文章受原作者版权保护。转载请注明原作者出处！