部分背包与01背包问题
阅读目录(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 = 0
left_capacity = V
for each item in items:
if left_capacity >= item.w:
// 可以拿全部
total_value += item.v
left_capacity -= item.w
else:
// 只能拿一部分
total_value += item.ratio * left_capacity
break // 背包已满，退出循环
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)
// 初始化一个 (n+1) x (V+1) 的二维数组dp，所有元素初始为0
dp = array[0..n][0..V] of 0
for i from 1 to n: // i 从1开始，对应第i件物品（索引为i-1）
for 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时的最大价值
复制代码