什么是网站建设和维护,在线编程的网站,网站没有关键词的弊端,2022中国进入一级战备了吗目录
一、动态规划简介
二、0/1背包问题概述
三、动态规划解决0/1背包问题
1. 定义子问题
2. 确定状态
3. 初始条件和边界情况
4. 计算最终结果
5. 代码实现
6. 空间优化
四、例题讲解
例题1#xff1a;基础例题
例题2#xff1a;路径恢复
例题3#xff1a;扩展…目录
一、动态规划简介
二、0/1背包问题概述
三、动态规划解决0/1背包问题
1. 定义子问题
2. 确定状态
3. 初始条件和边界情况
4. 计算最终结果
5. 代码实现
6. 空间优化
四、例题讲解
例题1基础例题
例题2路径恢复
例题3扩展问题
五、总结 动态规划Dynamic Programming, DP是计算机科学中一种解决复杂问题的高效方法。通过将问题分解成更小的子问题并存储其结果动态规划避免了重复计算从而显著提高了效率。本文将详细介绍动态规划的基本概念并以经典的0/1背包问题为例展示如何应用动态规划进行求解。
一、动态规划简介
动态规划是一种优化技术适用于解决具有重叠子问题和最优子结构性质的问题。其核心思想是通过记录已解决的子问题的结果避免重复计算从而提高算法效率。
动态规划的步骤通常包括
定义子问题将原问题分解为更小的子问题。确定状态定义表示子问题的状态变量。状态转移方程找到状态之间的递推关系。初始条件和边界情况设定初始状态的值。计算最终结果根据递推关系和初始条件计算出原问题的解。
二、0/1背包问题概述
0/1背包问题是组合优化中的经典问题之一其定义如下
给定一个容量为 W的背包以及 n个物品每个物品有一个重量 wi和价值 vi。在保证总重量不超过背包容量的前提下如何选择物品使得总价值最大
与之不同的是每个物品只能选择一次即0/1选择而不是无限制地选择完全背包问题。
三、动态规划解决0/1背包问题
1. 定义子问题
设 dp[i][j]表示前 iii 个物品在背包容量为 jjj 时的最大总价值。目标是求 dp[n][W]。
2. 确定状态
状态 dp[i][j]dp[i][j]dp[i][j] 的值可以通过以下方式递推得到
如果不选择第 i个物品则 dp[i][j]dp[i−1][j]dp[i][j] dp[i-1][j]dp[i][j]dp[i−1][j]。如果选择第 i个物品则 dp[i][j]dp[i−1][j−wi]vi前提是j ≥ wi。
因此状态转移方程为 dp[i][j]max(dp[i−1][j],dp[i−1][j−wi]vi)
3. 初始条件和边界情况
对于初始条件当没有物品或背包容量为0时总价值均为0
dp[0][j] 0 对于0≤j≤W
dp[i][0] 0 对于0≤i≤n
4. 计算最终结果
通过自底向上填充DP表格最终结果即为 dp[n][W]。
5. 代码实现
以下是C实现代码中包含了详细的解释
#include iostream #include vector #include algorithm
using namespace std;
int knapsack(const vectorint weights, const vectorint values, int W) { int n weights.size(); // 创建一个二维数组 dp大小为 (n1) x (W1)并初始化为 0 vectorvectorint dp(n 1, vectorint(W 1, 0)); // 填充 dp 表格 for (int i 1; i n; i) { for (int w 0; w W; w) { if (weights[i-1] w) { // 如果可以放入当前物品选择放或不放取最大值 dp[i][w] max(dp[i-1][w], dp[i-1][w - weights[i-1]] values[i-1]); } else { // 如果不能放入当前物品直接取前 i-1 个物品的最大值 dp[i][w] dp[i-1][w]; } } } // 最终结果是 dp[n][W]即考虑所有物品在最大重量 W 时的最大价值 return dp[n][W]; }
int main() { vectorint weights {2, 3, 4, 5}; vectorint values {3, 4, 5, 6}; int W 5; cout Maximum value in Knapsack knapsack(weights, values, W) endl; return 0; }
6. 空间优化
上述实现的时间复杂度为 O(nW)空间复杂度同样为 O(nW)。可以通过空间优化将空间复杂度降至 O(W)。这是因为在计算 dp[i][j]时只需要参考 dp[i−1][j]和 dp[i−1][j−wi] 两个状态因此可以使用一维数组进行优化。
优化后的实现如下
#include iostream #include vector #include algorithm
using namespace std;
int knapsack_optimized(const vectorint weights, const vectorint values, int W) { int n weights.size(); vectorint dp(W 1, 0); // 通过一维数组优化空间复杂度 for (int i 0; i n; i) { for (int w W; w weights[i]; --w) { dp[w] max(dp[w], dp[w - weights[i]] values[i]); } } return dp[W]; }
int main() { vectorint weights {2, 3, 4, 5}; vectorint values {3, 4, 5, 6}; int W 5; cout Maximum value in Knapsack knapsack_optimized(weights, values, W) endl; return 0; }
四、例题讲解
例题1基础例题
题目给定一个背包的容量为 5以及 4 个物品每个物品的重量和价值分别为 {2, 3, 4, 5} 和 {3, 4, 5, 6}。求如何选择物品使得总价值最大。
#include iostream #include vector #include algorithm
using namespace std;
int knapsack(const vectorint weights, const vectorint values, int W) { int n weights.size(); vectorvectorint dp(n 1, vectorint(W 1, 0)); // 填充 dp 表格 for (int i 1; i n; i) { for (int w 0; w W; w) { if (weights[i-1] w) { // 如果可以放入当前物品选择放或不放取最大值 dp[i][w] max(dp[i-1][w], dp[i-1][w - weights[i-1]] values[i-1]); } else { // 如果不能放入当前物品直接取前 i-1 个物品的最大值 dp[i][w] dp[i-1][w]; } } } return dp[n][W]; }
int main() { vectorint weights {2, 3, 4, 5}; vectorint values {3, 4, 5, 6}; int W 5; cout Maximum value in Knapsack knapsack(weights, values, W) endl; return 0; }
代码解释
初始化 dp 数组用于存储子问题的解。双重循环填充 dp 表格其中 dp[i][w] 表示前 i 个物品在容量为 w 时的最大价值。根据物品是否放入背包来更新 dp[i][w] 的值。最后返回 dp[n][W]即为最大总价值。
例题2路径恢复
题目求解背包问题的同时找出选择的物品。
#include iostream #include vector #include algorithm
using namespace std;
pairint, vectorint knapsack_with_items(const vectorint weights, const vectorint values, int W) { int n weights.size(); vectorvectorint dp(n 1, vectorint(W 1, 0)); vectorvectorbool keep(n 1, vectorbool(W 1, false)); // 填充 dp 表格并记录是否选择物品 for (int i 1; i n; i) { for (int w 0; w W; w) { if (weights[i-1] w) { if (dp[i-1][w] dp[i-1][w - weights[i-1]] values[i-1]) { dp[i][w] dp[i-1][w - weights[i-1]] values[i-1]; keep[i][w] true; } else { dp[i][w] dp[i-1][w]; } } else { dp[i][w] dp[i-1][w]; } } } // 回溯找出选择的物品 int w W; vectorint items; for (int i n; i 1; --i) { if (keep[i][w]) { items.push_back(i-1); w - weights[i-1]; } } return {dp[n][W], items}; }
int main() { vectorint weights {2, 3, 4, 5}; vectorint values {3, 4, 5, 6}; int W 5; auto result knapsack_with_items(weights, values, W); cout Maximum value in Knapsack result.first endl; cout Items included: ; for (int i : result.second) { cout i ; } cout endl; return 0; }
代码解释
在 dp 数组外增加一个 keep 数组用于记录是否选择某个物品。在填充 dp 表格时更新 keep 数组以记录选择情况。通过回溯 keep 数组找出选择的物品并存储在 items 数组中。最后返回最大总价值和选择的物品列表。
例题3扩展问题
题目考虑更多约束条件如物品的体积和背包的体积限制。
#include iostream #include vector #include algorithm
using namespace std;
struct Item { int weight; int volume; int value; };
int knapsack_with_volume(const vectorItem items, int W, int V) { int n items.size(); vectorvectorvectorint dp(n 1, vectorvectorint(W 1, vectorint(V 1, 0))); for (int i 1; i n; i) { for (int w 0; w W; w) { for (int v 0; v V; v) { if (items[i-1].weight w items[i-1].volume v) { dp[i][w][v] max(dp[i-1][w][v], dp[i-1][w - items[i-1].weight][v - items[i-1].volume] items[i-1].value); } else { dp[i][w][v] dp[i-1][w][v]; } } } } return dp[n][W][V]; }
int main() { vectorItem items { {2, 3, 4}, {3, 4, 5}, {4, 5, 6}, {5, 6, 7} }; int W 5; int V 7; cout Maximum value in Knapsack knapsack_with_volume(items, W, V) endl; return 0; }
代码解释
定义 Item 结构体包含物品的重量、体积和价值。初始化 dp 三维数组用于存储子问题的解。三重循环填充 dp 表格其中 dp[i][w][v] 表示前 i 个物品在重量为 w 和体积为 v 时的最大价值。根据物品是否放入背包来更新 dp[i][w][v] 的值。最后返回 dp[n][W][V]即为最大总价值。
五、总结
通过本文的详细解析和多个例题的讲解我们可以深入理解动态规划及其在0/1背包问题中的应用。从定义子问题、确定状态、推导状态转移方程、设定初始条件到计算最终结果动态规划提供了一种系统而高效的解决问题的思路。
掌握动态规划的基本原理和应用技巧不仅能解决背包问题还能扩展到其他领域如字符串匹配、序列比对、路径规划等。希望本文能够帮助读者更好地理解和应用动态规划提升解决复杂问题的能力。
