动态规划
基本概念
1.动态规划策略通常用于求解最优化问题。
在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的那个解，即最优解。
2.动态
在一定条件下，当前阶段的状态和下一阶段的状态之间的转移。
3.规划
建立状态转移方程（或称各阶段间的递推关系式），将各个阶段的状态以表格式方法存储。
表格式方法：用一个表来记录所有已解决的子问题的解。
基本思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而降低时间复杂性。
基本要素
1.最优子结构(optimal substructure)
原问题的最优解包含了子问题的最优解。该性质使我们能够以自底向上的方式从子问题的最优解逐步构造出原问题的最优解。
2.重叠子问题(overlapping subproblem)
有些子问题被反复使用多次（前一阶段的状态带到当前阶段，当前阶段的状态带到下一阶段）。
通过表格式方法来记录已解决的子问题的答案。
递推写法（柳神）
// 数塔为例
// 递推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])
// 如果非要建立dp数组，先要初始化dp[n][j] = f[n][j] [(j从1~n)]
// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]
// f[i][j]为第i行j列数字的大小
// 采用自底向上递推的方法
// 数组从1开始作为下标存储
for(int i = n - 1; i >= 1; i--) {
for(int j = 1; j <= i; j++)
f[i][j] += max(f[i+1][j], f[i+1][j+1]);
}
return f[1][1];
递归写法（柳神）
//不使用动态规划
int F(int n) {
if(n == 0 || n == 1) return 1;
else return F(n - 1) + F(n - 2);
}
// 此时F(5) = F(4) + F(3), F(4) = F(3) + F(2),3会被计算两次
// 采用动态规划的方法(记忆化搜索)
int dp[10000];
memeset(dp, -1, sizeof(dp));
int F(int n) {
if(n == 0 || n == 1) return 1;
if(dp[n] != -1) return dp[n];
else {
dp[n] = F(n-1) + F(n - 2);
return dp[n];
}
}
0-1背包问题
image.png
image.png
// 动态规划——0-1背包.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Item
{
int id;
int value;
int weight;
};
const int maxn = 1000;
bool isChosen[maxn];
int dp[maxn][maxn];
vector<Item>item;
vector<int>x;
int n;//物品数量
int c;//背包最大容量
void Knapsack()
{
for (int i = 0;i <= n;i++) dp[i][0] = 0;
for (int j = 0;j <= n;j++) dp[0][j] = 0;
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= c;j++)
{
if (j - item[i].weight >= 0)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item[i].weight] + item[i].value);
}
else
dp[i][j] = dp[i - 1][j];
}
}
}
void Traceback()
{
int j = c;
for (int i = n ;i >= 1;i--)
{
if (dp[i][j] > dp[i - 1][j])
{
isChosen[i] = true;
j -= item[i].weight;
}
else
isChosen[i] = false;
}
}
int main()
{
cin >> n >> c;
int value, weight;
item.resize(n + 1);
x.resize(n + 1);
for (int i = 1;i <= n;i++)
{
cin >> value >> weight;
item[i] = { i ,value,weight };//存储物品信息
}
Knapsack();
Traceback();
cout << "dp矩阵为" << endl;
for (int i = 1;i <= n;i++)
{
for (int j = 0;j <= c;j++)
{
cout << dp[i][j] << " ";
}
cout << endl;
}
for (int i = 1;i <= n;i++)
{
if (isChosen[i])
{
cout << "选择物品为：" << i << " ";
}
}
cout << "\n";
return 0;
}
image.png
