公司做网站好,网站开发加设计要多少钱,有趣网站之家,什么软件免费设计logo难度参考 难度#xff1a;困难 分类#xff1a;动态规划 难度与分类由我所参与的培训课程提供#xff0c;但需 要注意的是#xff0c;难度与分类仅供参考。且所在课程未提供测试平台#xff0c;故实现代码主要为自行测试的那种#xff0c;以下内容均为个人笔记#xff0…难度参考 难度困难 分类动态规划 难度与分类由我所参与的培训课程提供但需 要注意的是难度与分类仅供参考。且所在课程未提供测试平台故实现代码主要为自行测试的那种以下内容均为个人笔记旨在督促自己认真学习。
题目 动态规划经典问题01背包 具体内容 背包最大重量为4 物品如下
重量价值物品0115物品1320物品2430 问背包能背的最大重量是多少
思路 0-1 背包问题的动态规划解法基于以下思路 子问题定义 将原问题分解为子问题。在这里我们考虑对于给定的背包容量和一组物品最大价值是多少定义状态 dp[i][w] —— 表示考虑前 i 个物品时对于不超过 w 重量的背包所能得到的最大价值。 初始条件 对于 dp[0][...]即一个物品也不考虑的情况背包的价值总是 0。对于 dp[...][0]即背包容量为 0 的情况背包的价值也总是 0。 递推关系状态转移方程 对于每一个物品 i 和每一个可能的重量 w我们需要做出一个决策是否将物品 i 放入背包。如果不放物品 i则 dp[i][w] dp[i-1][w] —— 也就是说当前的最大价值与前 i-1 个物品时的最大价值相同。如果放物品 i我们必须确保当前背包的剩余容量至少是物品 i 的重量 (weights[i-1] w)在这种情况下dp[i][w] dp[i-1][w-weights[i-1]] values[i-1] —— 也就是说当前的最大价值是物品 i 的价值加上剩余重量在前 i-1 个物品中能得到的最大价值。 填表 我们按照递推关系来填表 —— 从较小的 i 和 w 开始直到 i 等于物品个数w 等于背包最大重量。 解的构造 表格填完后dp[n][maxWeight] 就是答案 —— 即考虑所有物品和最大背包重量时的最大价值。 补充-递推公式的推导 假设我们有n个物品每个物品的重量为weights[i]价值为values[i]背包的最大重量限制为maxWeight。我们定义dp[i][w]为考虑前i个物品物品编号为0到i-1在背包重量限制为w的情况下能够得到的最大总价值。我们想求的最终答案是dp[n][maxWeight]。 对于每个物品i从1开始计数对应数组下标为i-1以及每个可能的重量限制w我们面临两种选择 不包含当前物品如果我们决定不包含当前考虑的物品i-1那么最大价值不会因为当前物品的存在而改变所以它等于没有考虑当前物品时的最大价值即dp[i-1][w]。 包含当前物品如果我们决定包含当前考虑的物品i-1前提是这个物品的重量不超过当前的重量限制w即weights[i-1] w。此时我们需要加上这个物品的价值values[i-1]同时背包的剩余重量变为w - weights[i-1]因此我们还需要加上在新的重量限制下考虑前i-1个物品时的最大价值即dp[i-1][w-weights[i-1]] values[i-1]。 因此递推公式如下
如果weights[i-1] w当前物品重量超过背包限制则dp[i][w] dp[i-1][w]。否则dp[i][w] max(dp[i-1][w], dp[i-1][w-weights[i-1]] values[i-1])。 这个递推公式基于以下逻辑对于每个物品我们都做出是否包含它的决定以确保在不超过背包重量限制的情况下达到最大价值。这种方式确保了我们能够考虑所有可能的组合并找到最优解。
示例 初始状态 首先初始化一个表dp其中dp[i][j]代表在只考虑前i个物品且背包容量为j时的最大价值。初始化时所有值均为0。 物品情况 - 物品0价值15重量1 - 物品1价值20重量3 - 物品2价值30重量4 动态规划表格是这样的行表示物品列表示重量
重量 0 1 2 3 4
不选物品 0 0 0 0 0 加入物品0 加入物品0价值15重量1后我们更新表格。对于重量1及以上的列我们可以加入物品0。
重量 0 1 2 3 4
不选物品 0 0 0 0 0
加入物品0 0 15 15 15 15 加入物品1 接着我们考虑加入物品1价值20重量3。我们更新表格考虑对于每个重量限制在不超过该重量的情况下是否加入物品1能获得更高的价值。
重量 0 1 2 3 4
不选物品 0 0 0 0 0
加入物品0 0 15 15 15 15
加入物品1 0 15 15 20 20 在重量为4时我们比较加入物品1后的价值与之前的状态。但是我们忽略了一种可能加入物品1重量3价值20后还可以再加入物品0重量1价值15因此对于重量4最大价值应该是35物品0和物品1的组合。 加入物品2 最后我们考虑加入物品2价值30重量4。同样我们更新表格考虑对每个重量限制加入物品2是否能带来更高的价值。
重量 0 1 2 3 4
不选物品 0 0 0 0 0
加入物品0 0 15 15 15 15
加入物品1 0 15 15 20 35
加入物品2 0 15 15 20 35 在重量为4的情况下加入物品2的价值30并不比已有的组合物品0和物品1总价值35更优因此我们保持原有的最大价值不变。 最终结果 最终我们得到的动态规划表如下表明在背包重量限制为4时我们能获得的最大价值是35通过组合物品0价值15重量1和物品1价值20重量3。
重量 0 1 2 3 4
不选物品 0 0 0 0 0
加入物品0 0 15 15 15 15
加入物品1 0 15 15 20 35
加入物品2 0 15 15 20 35 因此最终答案是在确保总重量不超过4的条件下我们最后得到的背包中的最大价值是35。
梳理 这个方法能够实现的原因在于它利用了动态规划Dynamic Programming, DP的两个关键性质最优子结构和重叠子问题。 最优子结构意味着问题的最优解包含着其子问题的最优解。对于0-1背包问题来说每增加一个物品的选择都是基于之前所有物品选择的最优解上进行的新增决定。换句话说在考虑是否加入当前物品时我们可以依赖于之前物品的决策结果这些决策结果是以最大化价值为目标的。 重叠子问题指的是在解决问题的过程中相同的问题会被多次解决。在0-1背包问题中当我们分别计算每一个重量限制下的最大价值时会重复计算某些重量限制下的最大价值。通过动态规划我们可以将这些价值存储在一个表中避免重复计算这就是为什么我们使用一个二维数组来存储每个子问题的答案。 在填充动态规划表时我们从最小的子问题开始即背包没有任何物品时的价值是0。然后逐步增加物品和重量直到考虑了所有物品和所有重量限制。在每一步针对每一个重量限制我们都计算了两种情况 1. 不加入当前的物品直接使用之前同样重量限制下的最大价值。 2. 尝试加入当前的物品将物品的价值加上剩余重量限制下的最大价值。 通过比较上述两种情况的价值我们可以选择较大的一个作为当前重量限制和当前物品下的最大价值。这个过程一直持续到表格被填满最终我们在表格的右下角得到的值就是我们能够拿到的最大价值。 简单来说这方法之所以行之有效是因为它将一个复杂问题分解为一系列叠加的简单问题并解决它们同时保留了要求的全局最优解。通过表格的逐步填充我们保证了在任何给定重量限制下我们都是在做出最佳决策以此计算出全局最优解。 代码 #include iostream // 引入标准输入输出库
#include vector // 引入向量动态数组库
using namespace std; // 使用标准命名空间简化代码// 动态规划解决 0-1 背包问题的函数
int knapsack(const vectorint weights, const vectorint values, int maxWeight) {int n weights.size(); // 物品数量// 初始化动态规划表所有值起始为0vectorvectorint dp(n 1, vectorint(maxWeight 1, 0)); // 使用动态规划构建 dp 数组for (int i 1; i n; i) { // 遍历每个物品for (int w 1; w maxWeight; w) { // 遍历每种重量限制// 如果当前物品可以加入背包if (weights[i - 1] w) {// 选择加入当前物品和不加入当前物品中价值更大的一个dp[i][w] max(dp[i - 1][w], values[i - 1] dp[i - 1][w - weights[i - 1]]);} else {// 如果不能加入当前物品保持之前的最大价值dp[i][w] dp[i - 1][w];}}}// 返回最大值即考虑所有物品且不超过最大重量限制时的最大价值return dp[n][maxWeight];
}int main() {int maxWeight 4; // 背包的最大重量限制vectorint weights {1, 3, 4}; // 物品的重量vectorint values {15, 20, 30}; // 物品的价值// 输出背包能达到的最大总价值cout 背包能达到的最大总价值为 knapsack(weights, values, maxWeight) endl;return 0; // 程序正常结束
} 时间复杂度O(n * maxWeight) 空间复杂度O(n * maxWeight)
打卡
