动态规划与贪婪算法简记
一 动态规划算法
应用范围
如果是要求一个问题的最优解（通常是求最大值或最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决该问题。
我们在应用动态规划之前要分析能否把大问题分解成小问题，分解后的每个小问题也存在最优解。如果小问题的最优解组合起来能够得到整个问题的最优解，那么我们就可以应用动态规划解决这个问题。
可以应用动态规划求解的问题的四个特点
1.求一个问题的最优解；
2.整体问题的最优解是依赖各个子问题的最优解；
3.把大问题分解成若干个小问题，这些小问题之间还有相互重叠的更小的子问题；
4.由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，可以用从下往上的顺序先计算小问题的最优解并将其存储下来，再以此为基础求取大问题的最优解。从上往下分析问题，从下往上求解问题。
二 贪婪算法
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
应用范围
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择得到，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
动态规划与贪婪算法经典例子
一 动态规划算法经典例子之背包问题
0-1背包
题目：有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。
0-1背包问题：在最优解中，对于第i个物品只有两种可能的情况，在背包中和不在背包中（也就是背包中第i个物品的数量为0或1），因此称为0-1背包问题。
步骤1-找子问题：子问题必然是和物品有关的，对于第i个物品，有两种结果：能装下或者不能装下。第一，包的容量比物品体积小，装不下，这时的最大价值和前i-1个物品的最大价值是一样的。第二，还有足够的容量装下该物品，但是装了不一定大于当前相同体积的最优价值，所以要进行比较。由上述分析，子问题中物品数和背包容量都应当作为变量。因此子问题确定为背包容量为j时，求前i个物品所能达到最大价值。
步骤2-确定状态：由上述分析，“状态”对应的“值”即为背包容量为j时，求前i个物品所能达到最大价值，设为dp[i][j]。初始时，dp[0]j为0，也就是没有物品时当然也就没有价值。
步骤3-确定状态转移方程：由上述分析，第i个物品的体积为w,价值为v，则状态转移方程为
j<w，dp[i][j] = dp[i-1][j] //背包装不下该物品，最大价值不变
j>=w, dp[i][j] = max{ dp[i-1][j-list[i].w] + v, dp[i-1][j] } //此时背包中可以放下第i个物品，从dp[i-1][j-list[i].w]+v和dp[i-1][j]中选择较大的那个
//反向遍历j，方便接下来的优化处理，当然正向遍历也是可以的
struct Thing
{
int value; //物品的价值
int weight; //物品的重量
};
int max(int a, int b)
{
return a > b ? a : b;
}
void function01()
{
int n, s; //物品总数和背包容量
cout << "请输入物品总数n和背包容量s:";
cin >> n >> s;
int *vis = new int[n + 1]; //用于标示背包中包含了哪些物品
for (int i = 0; i <= n; ++i)
vis[i] = 0;
Thing *list = new Thing[n+1]; //申请物品空间
int **dp = new int*[n+1]; //指针数组申请空间
for (int i = 0; i <= n; ++i)
dp[i] = new int[s+1];
for (int i = 1; i <= n; ++i)
{
cout << "请输入第" << i << "个物品的重量和价值:";
cin >> list[i].weight >> list[i].value; //输入每个物品的重量和价值
}
for (int i = 0; i <= s; ++i)
dp[0][i] = 0; //没有物品当然也就没有价值可言
for (int i = 1; i <= n; ++i) //循环每个物品，执行状态转移方程
{
for (int j = s; j >= list[i].weight; j--) //反向从后向前遍历j，能够装下第i个物品
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - list[i].weight] + list[i].value);
for (int j = list[i].weight - 1; j >= 0; j--) //不能装下第i个物品
dp[i][j] = dp[i - 1][j];
} // end of for loop
for (int i = n, j = s; i >= 1; --i)
{
if (dp[i - 1][j] < dp[i - 1][j - list[i].weight] + list[i].value && j>= list[i].weight)
{
vis[i] = 1;
j = j - list[i].weight;
}
}
cout << "背包容量为" << s << "和物品数量为" << n << "时选择如下物品:";
for (int i = 0; i <= n; ++i)
if (vis[i] == 1)
cout << i;
cout << "可以得到最大价值" << dp[n][s] << endl;
/*cout << "背包容量为" << s << "时从" << n << "个物品中进行挑选能够得到的最大价值是"
<< dp[n][s] << endl;*/
for (int i = 0; i <= n; ++i)
delete[] dp[i];
delete[] dp;
delete[] list;
delete[] vis;
}当然我们也可以申请一个二维的vis标记数组来表示背包选择了哪些物品
struct Thing
{
int value; //物品的价值
int weight; //物品的重量
};
void function02()
{
int n, s; //物品总数和背包容量
cout << "请输入物品总数n和背包容量s:";
cin >> n >> s;
int **vis = new int*[n + 1];
for (int i = 0; i <= n; ++i)
vis[i] = new int[s + 1]{0};
Thing *list = new Thing[n + 1]; //申请物品空间
int **dp = new int*[n + 1]; //指针数组申请空间
for (int i = 0; i <= n; ++i)
dp[i] = new int[s + 1];
for (int i = 1; i <= n; ++i)
{
cout << "请输入第" << i << "个物品的重量和价值:";
cin >> list[i].weight >> list[i].value; //输入每个物品的重量和价值
}
for (int i = 0; i <= s; ++i)
dp[0][i] = 0; //没有物品当然也就没有价值可言
for (int i = 1; i <= n; ++i) //循环每个物品，执行状态转移方程
{
for (int j = 0; j <= s; ++j)
{
if (j >= list[i].weight)
{
if (dp[i - 1][j] < dp[i - 1][j - list[i].weight] + list[i].value)
{
vis[i][j] = 1;
dp[i][j] = dp[i - 1][j - list[i].weight] + list[i].value;
}
else
dp[i][j] = dp[i - 1][j];
}
//dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - list[i].weight] + list[i].value);
else
dp[i][j] = dp[i - 1][j];
}
}
vector<int>v;
for (int i = n, j = s; i >= 1;)
{
if (vis[i][j] == 1)
{
v.push_back(i);
j = j - list[i].weight;
--i;
}
else
--i;
}
cout << "背包容量为" << s << "和物品数量为" << n << "时选择如下物品:";
for (int i = static_cast<int>(v.size())-1; i >= 0; --i)
cout << v[i];
cout << "可以得到最大价值" << dp[n][s] << endl;
/*cout << "背包容量为" << s << "时从" << n << "个物品中进行挑选能够得到的最大价值是"
<< dp[n][s] << endl;*/
for (int i = 0; i <= n; ++i)
delete[] dp[i];
delete[] dp;
for (int i = 0; i <= n; ++i)
delete[] vis[i];
delete[] vis;
delete[] list;
}优化算法：观察状态转移方程的特点，我们发现dp[i][j]的转移只与dp[i-1][j-list[i].w]和dp[i-1][j]有关，即仅与二维数组本行的上一行有关。因此，我们可以将二维数组优化为一维数组。不过这里要注意两点：1.j<w的状态转移方程不再需要了，因为j<w时dp[i][j]=dp[i-1][j]。2.为保证每个物品只能使用一次，我们倒序遍历所有j的值，这样在更新dp[j]的时候，dp[j-list[i].w]的值尚未被修改，就不会出现一个物品重复使用的问题。
优化后的状态转移方程：dp[j] = max{ dp[j-list[i].w] + v, dp[j] }
struct Thing
{
int value; //物品的价值
int weight; //物品的重量
};
void function03() //将二维dp数组进行优化使用一维dp数组
{
int n, s; //物品总数和背包容量
cout << "请输入物品总数n和背包容量s:";
cin >> n >> s;
int **vis = new int*[n + 1];
for (int i = 0; i <= n; ++i)
vis[i] = new int[s + 1]{ 0 };
Thing *list = new Thing[n + 1]; //申请物品空间
int *dp = new int[s + 1]; //申请动态数组空间
for (int i = 1; i <= n; ++i)
{
cout << "请输入第" << i << "个物品的重量和价值:";
cin >> list[i].weight >> list[i].value; //输入每个物品的重量和价值
}
for (int i = 0; i <= s; ++i)
dp[i] = 0; //没有物品当然也就没有价值可言
for (int i = 1; i <= n; ++i) //循环每个物品，执行状态转移方程
{
for (int j = s; j >= list[i].weight; --j)
{
if (dp[j] < dp[j - list[i].weight] + list[i].value)
{
vis[i][j] = 1;
dp[j] = dp[j - list[i].weight] + list[i].value;
}
//dp[j] = max(dp[j], dp[j - list[i].weight] + list[i].value);
}
}
vector<int>v;
for (int i = n, j = s; i >= 1;)
{
if (vis[i][j] == 1)
{
v.push_back(i);
j = j - list[i].weight;
--i;
}
else
--i;
}
cout << "背包容量为" << s << "和物品数量为" << n << "时选择如下物品:";
for (int i = static_cast<int>(v.size()) - 1; i >= 0; --i)
cout << v[i];
cout << "可以得到最大价值" << dp[s] << endl;
/*cout << "背包容量为" << s << "时从" << n << "个物品中进行挑选能够得到的最大价值是"
<< dp[s] << endl;*/
delete[] dp;
for (int i = 0; i <= n; ++i)
delete[] vis[i];
delete[] vis;
delete[] list;
}变式：要求恰好装满背包时，把dp[0]0设为0，其余dp[0]i设为负无穷即可，
这样只有恰好达到dp[n]s时，也就是刚好装满背包，dp[n]s才为正值，因此最后如果dp[n]s的值小于0表示没有适当的方式装满背包，大于0说明找到了装满背包的最大价值物品，其中括号中表示使用优化算法的。
struct Thing
{
int value; //物品的价值
int weight; //物品的重量
};
void function04() //将二维dp数组进行优化使用一维dp数组且要求刚好填满背包
{
int n, s;//物品总数和背包容量
cout << "请输入物品总数n和背包容量s:";
cin >> n >> s;
int **vis = new int*[n + 1];
for (int i = 0; i <= n; ++i)
vis[i] = new int[s + 1]{ 0 };
Thing *list = new Thing[n + 1]; //申请物品空间
int *dp = new int[s + 1]; //申请动态数组空间
for (int i = 1; i <= n; ++i)
{
cout << "请输入第" << i << "个物品的重量和价值:";
cin >> list[i].weight >> list[i].value; //输入每个物品的重量和价值
}
dp[0] = 0;
for (int i = 1; i <= s; ++i)
dp[i] = INF; //没有物品当然也就没有价值可言，设置为负无穷大
for (int i = 1; i <= n; ++i) //循环每个物品，执行状态转移方程
{
for (int j = s; j >= list[i].weight; --j)
{
if (dp[j] < dp[j - list[i].weight] + list[i].value)
{
vis[i][j] = 1;
dp[j] = dp[j - list[i].weight] + list[i].value;
}
//dp[j] = max(dp[j], dp[j - list[i].weight] + list[i].value);
}
}
vector<int>v;
for (int i = n, j = s; i >= 1;)
{
if (vis[i][j] == 1)
{
v.push_back(i);
j = j - list[i].weight;
--i;
}
else
--i;
}
cout << "背包容量为" << s << "和物品数量为" << n << "时选择如下物品:";
for (int i = static_cast<int>(v.size()) - 1; i >= 0; --i)
cout << v[i];
cout << "可以得到最大价值" << dp[s] << endl;
/*cout << "背包容量为" << s << "时从" << n << "个物品中进行挑选能够得到的最大价值是"
<< dp[s] << endl;*/
delete[] dp;
for (int i = 0; i <= n; ++i)
delete[] vis[i];
delete[] vis;
delete[] list;
}完全背包问题
我们扩展0-1背包问题，使每种物品的数量无限增加，便得到完全背包问题：有一个容积为 V 的背包，同时有 n 个物品，每个物品均有各自的体积 w 和价值 v，每个物品的数量均为无限个，求使用该背包最多能装的物品价值总和。
正好利用了上述0-1背包的优化算法，这时我们正序遍历j，正好可以实现每种物品的重复利用，即相当于每种物品有无限个。
int max(int a, int b)//取最大值函数
{
return a > b ? a : b;
}
struct Thing
{
int weight;
int value;
};
struct combination
{
int number; //物品编号
int count; //物品number出现的次数，也就是背包中选择物品number的次数
};
void function05() //完全背包问题，每种物品有无限个
{
int n, s; //物品总数和背包容量
cout << "请输入物品总数n和背包容量s:";
cin >> n >> s;
int **vis = new int*[n + 1]; //标示数组用于背包中是否包含某种物品
for (int i = 0; i <= n; ++i)
vis[i] = new int[s + 1]{ 0 };
Thing *list = new Thing[n + 1]; //申请物品空间
int *dp = new int[s + 1]; //申请动态数组空间
for (int i = 1; i <= n; ++i)
{
cout << "请输入第" << i << "个物品的重量和价值:";
cin >> list[i].weight >> list[i].value; //输入每个物品的重量和价值
}
for (int i = 0; i <= s; ++i)
dp[i] = 0; //没有物品当然也就没有价值可言
for (int i = 1; i <= n; ++i) //正序遍历每个物品，执行状态转移方程，这样前面的物品就可以实现重复利用了
{
for (int j = list[i].weight; j <= s; ++j)
{
if (dp[j] < dp[j - list[i].weight] + list[i].value)
{
vis[i][j] = 1;
dp[j] = dp[j - list[i].weight] + list[i].value;
}
//dp[j] = max(dp[j], dp[j - list[i].weight] + list[i].value);
}
}
vector<combination>v;
int count = 0;
for (int i = n, j = s; i >= 1;)
{
count = 0;
while (vis[i][j] == 1)
{
++count; //统计背包中选择物品i的次数
j = j - list[i].weight;
}
combination tmp(i, count);
v.push_back(tmp);
--i;
}
cout << "背包容量为" << s << "和物品数量为" << n << "时选择如下物品:" << endl;
for (int i = static_cast<int>(v.size()) - 1; i >= 0; --i)
cout << "物品" << v[i].number << "选择" << v[i].count << "个" << endl;
cout << "可以得到最大价值" << dp[s] << endl;
/*cout << "背包容量为" << s << "时从" << n << "个物品中进行挑选能够得到的最大价值是"
<< dp[s] << endl;*/
delete[] dp;
for (int i = 0; i <= n; ++i)
delete[] vis[i];
delete[] vis;
delete[] list;
}完全背包问题的一个例子
在ACM可以做任何事情之前，必须准备预算并获得必要的财务支持。此操作的主要收入来自不可逆绑定资金（IBM）。背后的想法很简单。每当ACM成员有少量钱时，他就会拿走所有硬币并将它们扔进存钱罐。您知道此过程是不可逆的，如果不破坏猪就无法取出硬币。经过足够长的时间后，存钱罐中应该有足够的现金来支付所有需要支付的款项。
但是存钱罐有一个大问题。无法确定里面有多少钱。因此，我们可能将猪弄成碎片，只是发现没有足够的钱。显然，我们要避免这种不愉快的情况。唯一的可能性是称量存钱罐，然后尝试猜测里面有多少硬币。假设我们能够准确地确定猪的重量，并且知道给定货币的所有硬币的重量。然后，我们可以保证存钱罐中有一些最低限度的钱。您的任务是找出最坏的情况，并确定存钱罐内的最小现金量。我们需要您的帮助。不再有过早损坏的猪！
#include<iostream>
usng namespace std;
int const INF = 0x7fffffff; //因为此时是求最小值，所以INF应为无穷大
int min(int a, int b){return a < b ? a : b;} //取最小值函数
struct Thing
{
int weight;
int value;
};
void function06()
{
int T; //测试组数
cin >> T;
int s, s1, s2, n; //硬币总重、空猪重量、满猪重量和硬币总类型数
cin >> s1 >> s2; //读入空猪重量和满猪重量
s = s2 - s1; //得到硬币总重
while (T--)
{
cin >> n; //读入硬币总类型数
Thing *list = new Thing[n+1]; //申请数组存放硬币属性信息
for (int i = 1; i <= n; i++)
{
cin >> list[i].value >> list[i].weight; //读入每个物品的价值和重量
}
int *dp = new int[s + 1];
dp[0] = 0; //为了实现刚好硬币总量等于给定值，我们设置dp[0]=0
for (int i = 1; i <= s; i++) dp[i] = Inf; //其他的初始化为无穷大
for (int i = 1; i <= n; i++) //循环每个物品，正序遍历j执行状态转移方程
{
for (int j = list[i].weight; j <= s; j++)
{
if (dp[j - list[i].weight] != Inf) dp[j] = min(dp[j],
dp[j - list[i].weight] + list[i].value);
//如果dp[j - list[i].weight]不为无穷，就可以由此状态转移而来
}
}
if (dp[s] != Inf)
cout << "The minimum amount of money in the piggy-bank is" <<dp[s] << endl;
else
cout << "This is impossible." << endl;
delete[] list;
delete[] dp;
}
}多重背包问题
多重背包问题介于 0-1 背包和完全背包之间：有容积为V的背包，给定一些物品，每种物品包含体积 w、价值 v、和数量 k，求用该背包能装下的最大价值总量。
与之前讨论的问题一样，我们可以将多重背包问题直接转化到 0-1 背包上去，即每种物品均被视为k种不同物品，对所有的物品求0-1背包。其时间复杂度为O(s*Σki)。
由此可见，降低每种物品的数量 ki 将会大大的降低其复杂度，于是我们采用一种更为有技巧性的拆分。将原数量为 k 的物品拆分为若干组，每组物品看成一件物品，其价值和重量为该组中所有物品的价值重量总和，每组物品包含的原物品个数分别为：为：1、2、4…k-2^c+1，其中 c 为使 k-2^c+1 大于 0 的最大整数。这种类似于二进制的拆分，不仅将物品数量大大降低，同时通过对这些若干个原物品组合得到新物品的不同组合，可以得到 0 到 k 之间的任意件物品的价值重量和，所以对所有这些新物品做 0-1 背包，即可得到多重背包的解。由于转化后的 0-1 背包物品数量大大降低，其时间复杂度也得到较大优化，为O(s*Σlog2(ki))。
二 贪婪算法经典例子之活动安排问题
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意：可以认为区间的终点总是大于它的起点。区间[1,2]和[2,3]的边界相互“接触”，但没有相互重叠。
示例1：
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
解题思路
贪心策略:统计不重合的最大区间集合总数，所有区间的数量-不重合的最大区间集合总数=删除的重叠区间数。 按照每个区间的右端点排序（结束时间最早，比如你一天要参加几个活动，这个活动开始的多早其实不重要，重要的是你结束的多早，早晨7点就开始了然后一搞就搞了一整天，那你今天也就只能参加这一个活动；但如果这个活动开始的不早，比如9点才开始，但是随便搞搞10点就结束了，那你接下来就还有大半天的时间可以参加其他活动），将第一个区间的end设置为默认end，依次遍历排序后的其他区间，进行重叠性判断。
代码如下
int eraseOverlapIntervals(vector<vector<int>>& intervals)
{
if(intervals.empty())
return 0;
sort(intervals.begin(),intervals.end(),cmp);
int cnt=1;
int tmp_end=intervals[0][1]; //第一个区间的结束时间
for(int i=1;i<intervals.size();++i)
{
int start=intervals[i][0]; //第i个区间的开始时间
int end=intervals[i][1]; //第i个区间的结束时间
if(start<tmp_end) //相等不是重合,当前区间的开始时间在前一个区间的结束时间之前
continue;
++cnt;
tmp_end=end;
}
return intervals.size()-cnt;
}
bool cmp(vector<int>a1,vector<int>a2) //自定义排序算法，先按结束时间排序，结束时间相同的话就再按开始时间排序
{
if(a1[1]==a2[1])
return a1[0]<a2[0];
return a1[1]<a2[1];
}
京公网安备 11010502036488号