您的位置:首页 >资讯>中华武术

聊聊十五周算法训练营——背包问题 全球速看

2023-06-27 23:20:52 来源:清一色财经 收藏

「背包问​题:给你一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i],价值为val[i],现在让你用这个背包装物品,最多能装的价值是多少?」

今天是十五周算法训练营的第十三周,主要讲背包问题专题。(欢迎加入十五周算法训练营,与小伙伴一起卷算法)


(资料图片)

「背包问题:给你一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i],价值为val[i],现在让你用这个背包装物品,最多能装的价值是多少?」

0-1背包动态规划思路

明确状态和选择

状态有两个:背包的容量和可选择的物品

选择就是:装进背包或者不装进背包

dp数组的含义

刚才明确了状态,现在需要用dp数组把状态表达出来,刚才找到的「状态」,有两个,也就是说我们需要一个二维dp数组,一维表示可选择的物品,一维表示背包的容量。

dp[i][w]表示的就是对于[0……i]个物品,当前背包容量为w时的最大价值

根据选择,思考状态转移的逻辑

dp[i][w]表示:对于前i个物品,当前背包的容量为w时,这种情况下可以装下的最大价值是dp[i][w]。

如果你没有把这第i个物品装入背包,那么很显然,最大价值dp[i][w]应该等于dp[i-1][w]。你不装嘛,那就继承之前的结果。

如果你把这第i个物品装入了背包,那么dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]。

首先,由于i是从 1 开始的,所以对val和wt的取值是i-1。

明确base case: 此处的base case就是dp[ 0 ][ …… ]和dp[……][0]的时候,这个时候没有物品或者背包没有容量,此时价值为0

背包问题动态规划的结构

for 状态1 in 状态1的所有取值:    for 状态2 in 状态2的所有取值:        for ...            dp[状态1][状态2][...] = 择优(选择1,选择2...)

0-1背包解题思路

/** * 0-1背包问题解题思路 *  * 给你一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i],价值为val[i],现在让你用这个背包装物品,最多能装的价值是多少? */// 该问题是一个典型的动态规划问题// 1. 明确状态和选择// 状态就是背包的容量和可选的物品// 选择就是要不要装该物品// 2. dp数组含义// dp[i][w]表示前i个物品、当前背包容量为w时,能装的最大价值// 3. 状态转移逻辑// 为了获取dp[i][w]的时候需要考虑当前要放入物品的重量是否可以放到背包中,即比较当前背包容量和要放入物品重量// 若不能放进去:dp[i][w] = dp[i - 1][w]// 若可以放进去,则此时就需要比较放入和不放入后的价值dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wtPresent] + valPresent)function knapsack(W, N, wt, val) {    // 定义dp    const dp = new Array(N + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(W + 1)).fill(0);    }    // base case    // 当在定义dp的时候已经进行了初始化为0,0就是起base case    for (let i = 1; i < dp.length; i++) {        for (let w = 1; w < dp[0].length; w++) {            // 判断当前物品是否可以放到背包中,如果不能放进去            if (w - wt[i - 1] < 0) {                dp[i][w] = dp[i - 1][w];            } else {                // 如果可以放进去                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);            }        }    }    // 最终结果    return dp[N][W];}

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。

// 对于经典背包问题,是给你一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i],价值为val[i],现在让你用这个背包装物品,最多能装的价值是多少?// 该问题其实是经典背包问题的变形,可以先对集合求和,得出sum,该问题就可以转换为背包问题:// 给一个可装载重量为sum / 2的背包和N个物品,每个物品的重量为nums[i],现在让你装物品,是否存在一种装法,能够恰好将背包装满// 1. 明确状态和选择// 状态就是背包容量和可选择的物品// 选择就是装进背包和不装进背包// 2. dp数组函数// dp[i][j] = x表示,对于前i个物品,当前背包的容量为j时,若x为true,则说明可以恰好将背包装满,若x为false,则说明不能恰好将背包装满。// 3. 状态转移逻辑// 若放不进去,dp[i][j] = dp[i - 1][j]// 若能够放进去dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]// 4. base case// base case就是:// (1)有物品但是容量为0,肯定能装满,此时即dp[……][0] = true// (2)没有物品但是有容量时,肯定装不满,此时即dp[0][……] = falsefunction canPartition(nums) {    let sums = 0;    nums.forEach(num => sums += num);    // 如果是奇数,不能被划分,直接返回false    if (sums % 2 === 1) {        return false;    }    const numsLen = nums.length;    const dp = new Array(numsLen + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(sums / 2 + 1)).fill(false);    }    // base case    for (let i = 0; i < dp.length; i++) {        dp[i][0] = true;    }    for (let i = 1; i < dp.length; i++) {        for (let j = 1; j < dp[0].length; j++) {            if (j - nums[i - 1] < 0) {                dp[i][j] = dp[i - 1][j];            } else {                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];            }        }    }    // 最终其dp[n][sum / 2]就是起结果,因为此时能找到和的一半,另一半也是和的一半    return dp[numsLen][sums / 2];}

零钱兑换II

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1:

输入:amount = 5, coins = [1, 2, 5] 输出:4 解释:有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

// 该问题可转换为有一个背包,最大容量为amount,有一系列物品coins,每个物品的重量为coins[i],每个物品的数量无限。请问有多少种方法,能够把背包恰好装满?// 与经典背包区别的是每个物品的数量是无限的,这也就是完全背包问题。// 1. 状态和选择// 状态:背包的容量和可选择的物品// 选择:放进背包和不放进背包// 2. 定义dp// dp[i][j]:若只使用前i个物品,当背包容量为j时,有dp[i][j]种方法可以装满背包。换句话说:若只使用coins中的前i个硬币的面值,若想凑出金额j,有dp[i][j]中凑法// 3. 状态转移逻辑// 若不能放进去:dp[i][j] = dp[i - 1][j]// 若能够放进去:dp[i][j] = dp[i - 1][j] + dp[i - 1][j - coins[i]]// 4. base case// (1)有硬币,但是目标结果为0,即dp[0……n][0] = 1// (2)没有硬币,即dp[0][0……n] = 0function change(amount, coins) {    const n = coins.length;    const dp = new Array(n + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(amount + 1)).fill(0);    }    // base case    for (let i = 0; i < dp.length; i++) {        dp[i][0] = 1;    }    // 遍历dp    for (let i = 1; i < dp.length; i++) {        for (let j = 1; j < dp[0].length; j++) {            // 如果当前硬币不能放进背包            if (j < coins[i - 1]) {                dp[i][j] = dp[i - 1][j];            } else {                // 能放进去,则结果就是放进去与不放进去的加和                // 为什么当放进去的时候为i,因为此时已经决定使用coins[i - 1]的值                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];            }        }    }    // 目标结果就是[N, amount]    return dp[n][amount];}// 通过观察发现dp[i][j]之和dp[i][……]和dp[i - 1][……]相关// 则可进行状态压缩function change1(amount, coins) {    // 定义dp    const dp = (new Array(amount + 1)).fill(0);    // base case    dp[0] = 1;    // 进行遍历    for (let i = 0; i < coins.length; i++) {        for (let j = 1; j < dp.length; j++) {            if (j >= coins[i]) {                dp[j] = dp[j] + dp[j - coins[i]];            }        }    }    return dp[dp.length - 1];}const amount = 5;const coins = [1, 2, 5];console.log(change1(amount, coins));

最后一块石头的重量II

有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎; 如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。 最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。

示例 1:

输入:stones = [2,7,4,1,8,1] 输出:1 解释: 组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1], 组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1], 组合 2 和 1,得到 1,所以数组转化为 [1,1,1], 组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。

// 该问题和分割等和子集问题(416)处理方式类似,就是背包问题// 1. 状态和选择// 状态:背包和当前可选物品// 选择:是否装进背包// 2. dp数组含义// dp[w][i]表示背包容量为w时,前i个物品,最多能够装的物品重量// 3. 状态转移逻辑// 不能装进去:dp[w][i] = dp[w][i - 1]// 能够装进去:dp[w][i] = Math.max(dp[w][i - 1], dp[w - stones[i]][i - 1] + stones[i])// 4. base case// 当i = 0时,dp[0……w][0] = 0// 当w = 0时,dp[0][……] = 0function lastStoneWeightII(stones) {    // 得到总重量    let sum = 0;    stones.forEach(stone => {        sum += stone;    });    const weight = Math.floor(sum / 2);    // 定义dp    const dp = new Array(weight + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(stones.length + 1)).fill(0);    }    // base case 在初始化时已经完成    // 循环遍历    for (let w = 1; w < dp.length; w++) {        for (let i = 1; i < dp[0].length; i++) {            // 判断是否可以装进去            if (w - stones[i - 1] < 0) {                dp[w][i] = dp[w][i - 1];            } else {                dp[w][i] = Math.max(dp[w][i - 1], dp[w - stones[i - 1]][i - 1] + stones[i - 1]);            }        }    }    return sum - 2 * dp[weight][stones.length];}const stones = [31,26,33,21,40];console.log(lastStoneWeightII(stones));

目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ,然后串联起所有整数,可以构造一个 表达式 :

例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-‘ ,然后串联起来得到表达式 “+2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1:

输入:nums = [1,1,1,1,1], target = 3 输出:5 解释:一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 – 1 + 1 + 1 + 1 = 3 +1 + 1 – 1 + 1 + 1 = 3 +1 + 1 + 1 – 1 + 1 = 3 +1 + 1 + 1 + 1 – 1 = 3

// 该方法可以用背包解决// 如何转换为01背包问题呢?// 假设加法的总和为x,那么减法对应的总和就是sum - x// 所以我们要求的就是x - (sum - x) = S// x = (S + sum) / 2// 此时问题就转化为:装满容量为x背包,有几种方法// 1. 状态和选择// 2. dp数组含义// dp[i][w]:前i个物品、背包容量为w时,有几种方式装满// 3. 状态转移逻辑// 装不进去:dp[i][w] = dp[i - 1][w]// 能装进去:dp[i][w] = dp[i - 1][w - nums[i]] + dp[i - 1][w]// 4. base case// dp[0][0] = 1function findTargetSumWays(nums, target) {    // 求和    const sum = nums.reduce((total, num) => total + num);    // weight必须大于0且为整数    if (target + sum < 0 || (target + sum) % 2 === 1) {        return 0;    }    // 求weight    const weight = (target + sum) / 2;    // dp    const dp = new Array(nums.length + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(weight + 1)).fill(0);    }    // base case    dp[0][0] = 1;    // 循环    for (let i = 1; i < dp.length; i++) {        for (let w = 0; w < dp[i].length; w++) {            // 不能装进去            if (w - nums[i - 1] >= 0) {                dp[i][w] = dp[i - 1][w] + dp[i - 1][w - nums[i - 1]];            } else {                dp[i][w] = dp[i - 1][w];            }        }    }    return dp[nums.length][weight];}// 用回溯算法实现一遍function findTargetSumWays1(nums, target) {    let result = 0;    const backtrack = (index, sum) => {        // 结束条件        if (index === nums.length) {            if (sum === target) {                result++;            }            return;        }        backtrack(index + 1, sum + nums[index]);        backtrack(index + 1, sum - nums[index]);    };    backtrack(0, 0);    return result;}const nums = [0, 0, 0, 1];const target = 1;console.log(findTargetSumWays1(nums, target));

关键词:

相关的文章>>

标签:
「背包问​题:给你一个可装载重量为W的背包和N个物品,每个物品有重量[ 查看全文 ]
标签:
天津拟出让31块住宅用地涉及11个区,天津市,津南区,大运河,土地出让,土[ 查看全文 ]
标签:
6月11日清晨,在临近深圳的伶仃洋海域上,随着海底隧道的最终接头与海[ 查看全文 ]
标签:
6月26日,适逢第36个国际禁毒日,围绕“健康人生,绿色无毒”这一禁毒[ 查看全文 ]
标签:
2023年6月26日,河南新乡市凤泉区区长丁文广带队调研凤泉区重点项目,[ 查看全文 ]
标签:
中消协:加强演出票务运行、票源流向的监督管理探索建立全国统一的演出[ 查看全文 ]
标签:
苏州通过“双随机、一公开”抽查企业1861家多举措提升生态环境监管效能[ 查看全文 ]
标签:
郑报融媒把握正确舆论导向,关注百姓生活,侧重报道社会生活中的知识性[ 查看全文 ]
标签:
飞象网讯6月27日,中国移动在上海举办以“超越连接,智联未来”为主题[ 查看全文 ]
标签:
2023年注册会计师全国统一考试交费时间:2023年6月15日-6月30日(早8:0[ 查看全文 ]
标签:
任天堂对外公布近期举行的股东答疑会议内容,其中回应了为什么下代掌机[ 查看全文 ]
标签:
天眼查App显示,6月27日,支付宝(杭州)信息技术有限公司申请的“基于[ 查看全文 ]
标签:
包钢股份:包钢股份独立董事关于第七届董事会第三次会议审议相关事项的[ 查看全文 ]
标签:
铭凡UM560XT准系统迷你主机,目前京东热销价1280元,属于近期好价。主[ 查看全文 ]
标签:
日本首相岸田文雄7月11日起将出访欧洲和中东:日本首相岸田文雄表示,[ 查看全文 ]
标签:
据6月25日报道韩国美女主播、韩国小姐 李延济去世,年仅26岁据悉,李[ 查看全文 ]
标签:
全球范围内,推进绿色能源已成为当代社会的重要议题。越来越多的国家和[ 查看全文 ]
标签:
红米Note12Turbo目前京东售价2399元,下单可参加满2189元减401元促销活[ 查看全文 ]
标签:
油价又要变!国内油价第13轮调整或将在周三晚上迎来上涨,当前预计上涨[ 查看全文 ]
标签:
长城汽车,不知从何时起,一直站在舆论的风口浪尖。从各种奇葩车型命名[ 查看全文 ]

热门标签

热门搜索:

春季养生 健康问答 资讯

资讯

更多
  • 天津拟出让31块住...

  • 天天观热点:城市...

  • 快消息!魏都区人...

  • 每日速读!苏州通过...

  • 中国移动正式发布...

  • 任天堂回应新掌机...

图说健康

更多

体育健身

更多