企业官网建设流程全解析

网站制作致谢词,logo制作软件手机免费版,深圳市中心在哪,建站优化推广阅读目录(Content)一、部分背包问题二、01背包问题#xff1a;动态规划的入门在算法的学习中#xff0c;背包问题是一类经典的课题#xff0c;其中#xff0c;部分背包问题和01背包问题是两种最基础的形式。如果你想深入探索背包问题#xff0c;强烈推荐搜索“背包九讲”。…阅读目录(Content)一、部分背包问题二、01背包问题动态规划的入门在算法的学习中背包问题是一类经典的课题其中部分背包问题和01背包问题是两种最基础的形式。如果你想深入探索背包问题强烈推荐搜索“背包九讲”。一、部分背包问题问题描述假设我们有 n 件物品和一个容量为 V 的背包。每件物品 i 有其价值 v[i] 和重量 w[i]。在部分背包问题中我们可以选择物品的一部分放入背包例如金砂可以按克取即单样物品可以重复拿。我们的目标是如何选择物品使得装入背包的物品总价值最大核心思想贪心算法。因为这个问题不存在所谓的局部最优/全局最优只要有限拿最有价值的即可算是贪心算法的Hello World。贪心策略步骤计算所有物品的单位价值v[i] / w[i]将物品按单位价值从高到低排序。初始化当前背包剩余容量 left V 和总价值 total_value 0。遍历排序后的物品列表如果当前物品的重量 w[i] left说明背包还能装下整个物品那么就把它全部装入。total_value v[i]同时 left - w[i]。否则只能装入物品的一部分。装入 left 重量的该物品total_value (v[i] / w[i]) * left然后背包已满循环结束。伪代码实现复制代码function fractional_knapsack(v, w, V):n length(v)items [] // 创建一个列表存储物品索引、价值和重量for i from 0 to n-1:ratio v[i] / w[i]items.append((ratio, v[i], w[i], i)) // 将单位价值、价值、重量、索引打包sort items in descending order by ratio // 按单位价值降序排序total_value 0left_capacity Vfor each item in items:if left_capacity item.w:// 可以拿全部total_value item.vleft_capacity - item.welse:// 只能拿一部分total_value item.ratio * left_capacitybreak // 背包已满退出循环return total_value复制代码二、01背包问题动态规划的入门问题描述场景与部分背包类似但关键的区别在于对于每件物品我们要么完整地放入背包选择1要么完全不放入选择0不能只取一部分。这就是“01”的由来。即每样物品不能重复放入这个问题无法再用简单的贪心算法解决。这个问题主要演示动态规划的使用。什么是动态规划动态规划是一种通过把复杂问题分解为相对简单的子问题并存储子问题的解来避免重复计算从而高效解决问题的方法。即缓存之前步骤的结果重复使用我们只要定义好状态转移逻辑即类似dp[current]dp[current-1]dp[current-2] 这样的规则然后在代码里应用规则即可。可以想象为一张二维表每步每个选择的结果都出现在表中如需更详尽了解可网络上搜索一些教程。注意01背包问题使用动态规划解决因需要确保动态规划代码的简洁0下标元素留空步骤1从1下标的元素开始。伪代码实现复制代码function zero_one_knapsack(v, w, V):n length(v)// 初始化一个 (n1) x (V1) 的二维数组dp所有元素初始为0dp array[0..n][0..V] of 0for i from 1 to n: // i 从1开始对应第i件物品索引为i-1for j from 0 to V: // j 是当前背包容量if j w[i-1]:// 当前背包容量j小于物品i的重量装不下dp[i][j] dp[i-1][j]else:// 装得下在“不装”和“装”之间选择价值更大的方案dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i-1]] v[i-1])return dp[n][V] // 考虑前n件物品容量为V时的最大价值复制代码