网站开发api平台,教育行业网站,市北区网站建设,化学试剂网站建设目录 前置知识进入正题模板 前置知识 【算法】动态规划专题⑤ —— 0-1背包问题 滚动数组优化 完全背包问题是动态规划中的一种经典问题#xff0c;它与0-1背包问题相似#xff0c;但有一个关键的区别#xff1a;在完全背包问题中#xff0c;每种物品都有无限的数量可用。… 目录 前置知识进入正题模板 前置知识 【算法】动态规划专题⑤ —— 0-1背包问题 滚动数组优化 完全背包问题是动态规划中的一种经典问题它与0-1背包问题相似但有一个关键的区别在完全背包问题中每种物品都有无限的数量可用。也就是说你可以选择同一种物品多次放入背包以使背包中的总价值最大。
示例分析 假设物品重量为 (w [2, 3])价值为 (v [3, 4])容量 (C 5)
容量 (j)012345初始化000000物品1w2003366物品2w3003467
最优解选取 1 个物品1重量2价值3和 1 个物品2重量3价值4总价值为7。 进入正题 状态定义
设 dp[i][j] 表示前 (i) 种物品背包容量为 j 时的最大总价值。
状态转移方程的推导
核心思想
对第 (i) 种物品可以选择 0 次或多次因此需要枚举所有可能的选取次数。
暴力枚举
对每种物品 (i) 和容量 (j)假设选取 (k) 次物品 (i)则转移方程为 缺点时间复杂度为 (O(n * C * kmax)其中 kmax C/ w i w_i wi 效率极低。 优化推导消除对 k 的显式枚举
观察到以下递推关系 数学证明
假设在容量 (j) 时最优解中包含 (m \geq 1) 个物品 (i)则总价值为 dp[i][j] dp[ i i i][ j j j - w i w_i wi] v i v_i vi 这是因为在 ( j j j - w i w_i wi) 容量时已经考虑了选取 (m-1) 个物品 (i) 的最优解。
因此状态转移方程简化为 dp[i][j] max ( dp[i-1][j], dp[ i i i][ j j j - w i w_i wi] v i v_i vi ) 模板 完全背包问题 https://www.acwing.com/problem/content/3/
有 N N N 种物品和一个容量是 V V V 的背包每种物品都有无限件可用。 第 i i i 种物品的体积是 v i v_i vi价值是 w i w_i wi。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 输入格式 第一行两个整数 N V NV NV用空格隔开分别表示物品种数和背包容积。 接下来 N N N 行每行两个整数 v i , w i v_i, w_i vi,wi用空格隔开分别表示第 i i i 种物品的体积和价值。 输出格式 输出一个整数表示最大价值。 数据范围 0 N , V ≤ 1000 0 \lt N, V \le 1000 0N,V≤1000 0 v i , w i ≤ 1000 0 \lt v_i, w_i \le 1000 0vi,wi≤1000 输入样例
4 5
1 2
2 4
3 4
4 5输出样例
10code
n, v map(int, input().split())
dp [[0] * (v 1) for _ in range(n 1)]
for i in range(1, n 1):wi, vi map(int, input().split())for j in range(1, v 1):if j - wi 0:dp[i][j] max(dp[i - 1][j], dp[i][j - wi] vi)else:dp[i][j] dp[i - 1][j]
print(dp[n][v])滚动数组优化
n, v map(int, input().split())
dp [0] * (v 1)
for i in range(1, n 1):wi, vi map(int, input().split())for j in range(wi, v 1):dp[j] max(dp[j], dp[j - wi] vi)
print(dp[v])不了解 滚动数组优化 的可点此进入 END 如果有更多问题或需要进一步的帮助可以在评论区留言讨论哦 如果喜欢的话请给博主点个关注 谢谢
