贪心算法与动态规划的区别与联系

1.定义

1.1贪心算法的定义：

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

但是，局部最优解不一定是真正的最优方案，比如0-1背包问题，需要从整体考虑。

因此，贪心算法中正确性的证明是尤为重要的。

我们通常通过替换法来证明，通过将任意最优解的一部分和贪心解替换，看贪心解是否劣于最优解

1.2 动态规划的定义

动态规划其实和分治法很类似，都是把大问题分解为小问题。

不过动态规格用来解决重叠子问题的情况非常有利（分治法解决独立子问题），因为它有一个记事本功能，能把最优子结构记录下来，方便接下来的计算。因此我们需要自底向上计算。

动态规划和贪心的区别就是，他考察的全局的最优解。

分析问题的步骤很重要：

分析问题结果建立递推关系（找出最优子结构）自底向上计算最优方案追踪

2. 部分背包和0-1背包问题

2.1 部分背包和0-1背包的区别

部分背包中，每个物品可以分割成一部分，且背包和物品容量最小单位相同（类似于在水杯中倒不同价格的饮料）0-1背包中每个物品只有一个，所有情况只有不取或取（即0-1）,不可分割

因此，我们就可以直接使用性价比来分析问题。

2.2 部分背包

参赛者拥有容量为800ml的杯子，可任选不超过体积上限的饮料进行混合调制饮品价格为各所使用饮料的价格之和，所得饮品价格之和最高者获胜。

饮料价格（元）体积（ml）苏打水60600汽水10250橙汁36200果汁16100西瓜汁45300

第一行输入商品数量n和背包容量C，下面n行，每行输入该商品价格和体积 输入样例：

5 800 60 600 10 250 36 200 16 100 45 300

输出所得饮品价格之和 输出样例：

117 #include<iostream> #include<algorithm> #include<cmath> #include<string.h> using namespace std; typedef struct{ //re性价比；p价格；v体积 float re; int p; int v; }GOODS; bool cmp(GOODS& a,GOODS& b){ return a.re > b.re; } int main(){ //输入数据 int n,C; cin >> n>>C; GOODS g[n + 2]; for (int i = 0; i < n;i++){ cin >> g[i].p >> g[i].v; } //计算性价比 for (int i = 0; i < n;i++){ g[i].re = g[i].p * 1.0 / g[i].v; } //按性价比从大到小排序 sort(g, g + n, cmp); //根据贪心策略求解 int ans = 0; for (int i = 0; C > 0 && i < n;i++) { //商品体积不大于容器体积，全部倒入 if(C>=g[i].v){ ans += g[i].p; C -= g[i].v; } //当商品体积大于容器，取商品等于容器体积的那部分 else{ ans += g[i].p * C / g[i].v; C = 0; } } cout << ans << endl; return 0; }

该问题贪心解不劣于最优解

2.3 0-1背包

超市允许顾客使用一个体积大小为13的背包，选择1件或多件商品带走，如何带走总价最多的商品

商品价格体积啤酒2410汽水23饼干94面包105牛奶94

第一行输入商品数量n和背包容量C，下面n行，每行输入该商品价格和体积 输入样例：

5 13 24 10 2 3 9 4 10 5 9 4

输出样例：

选择的商品有：5 4 3 能装的最大的价值：28

分析：

找出最优子结构 p[i][j]表示：在前i个物品中选择，当背包容量为j时的价值最大 建立递推关系: if(背包容量j<v[i]) dp[i][j] = dp[i - 1][j]//不选该物品 if(背包容量j>v[i]) dp[i][j]=max(dp[i-1][j-v[i]]+w[i]，dp[i-1][j]);//看放入和不放入物品谁价值大，放入 背包容量-V[i]，价值+w[i];不放 dp[i][j]=dp[i-1][j]:

完整代码：

#include <bits/stdc++.h> #define N 10 using namespace std; int w[N]; //物品价值 int v[N]; //物品体积 int dp[10][100] = {0}; //前i个物品中选择，背包容量为j的最优解 bool rec[10][100] = {false}; //背包容量为j时，第i个物品是否被选择 int main() { //预处理 int n, c; //物品个数n,背包容量c scanf("%d %d", &n, &c); for (int i = 1; i <= n; i++) { scanf("%d %d", &w[i], &v[i]); } //动态规划 for (int i = 1; i <= n; i++){//第i个物品 for (int j = 1; j <= c; j++) //背包容量为j { //当背包容量小于物品 if (j < v[i]) dp[i][j] = dp[i - 1][j]; else//背包容量大于物品 { if (dp[i - 1][j - v[i]] + w[i] > dp[i - 1][j]) { dp[i][j] = dp[i - 1][j - v[i]] + w[i]; rec[i][j] = true; } else { dp[i][j] = dp[i - 1][j]; } } } } //最优方案追踪 printf("选择的商品有："); int t = c; for (int i = n; i > 0; i--) { if (rec[i][t]) { printf("%d ", i); t -= v[i]; } } printf("\n"); cout << "能装的最大的价值：" << p[n][c] << endl; return 0; }

3. 活动选择和加权版活动选择问题

3.1活动选择

活动选择问题是经典的贪心算法问题了，通过选择最早结束的活动，来给剩下的活动空出更多时间，以便求得最多活动数。

通过例题来看： 会场出租，选择出租的活动时间不能冲突，怎样选择才能选更多的活动？

第一行输入活动数n,下面有n行，每行输入活动开始时间和结束时间

输入样例：

11 1 4 3 5 0 6 4 7 3 9 5 9 6 10 8 11 8 12 2 14 12 16

输出所选活动，以空格分开 输出样例：

1 4 8 11 #include<bits/stdc++.h> using namespace std; typedef struct{ int start; int end; }ACTIVITY; bool cmp(ACTIVITY& a,ACTIVITY& b){ return a.end < b.end; } int main(){ //输入数据 int n; cin>>n; ACTIVITY act[n+1],ans[n+1]; for (int i = 0; i < n;i++){ cin >> act[i].start >> act[i].end; } //将活动以结束时间从小到大排序 sort(act, act + n, cmp); int index[n + 1];//记录所选活动 memset(index, 0, sizeof(index)); //最早结束的活动必选 ans[0] = act[0]; index[0] = 1; int j = 0; //找出所选活动结束后，最早开始的 for (int i = 1; i < n;i++){ if(act[i].start>=ans[j].end){ ans[++j] = act[i]; index[j] = i + 1; } } //输出所选活动 for (int i = 0; i <= j;i++){ cout << index[i] << " "; } cout << endl; return 0; }

该问题贪心解不劣于最优解。

3.2 加权版活动选择

会场出租，选择出租的活动时间不能冲突，活动出租收益各不相同，怎样选让收益总和最大? 第一行输入活动数n,下面有n行，每行输入活动开始时间和结束时间

输入样例：

10 1 4 1 3 5 6 0 6 4 4 7 7 3 9 3 5 9 12 6 10 2 8 11 9 8 12 11 2 14 8

输出所选活动，以空格分开 输出样例：

9 4 1

该问题很显然不能再用贪心计算。

我们看看能不能用动归：

首先分析问题：用dp[n]来表示集合{a1,a2,…,an}中不冲突活动的最大权重和

然后找出最优子结构：用dp[i]来表示集合{a1,a2,…,ai}中不冲突活动的最大权重和

重叠子问题：是否选择a[i] if选择a[i] dp[i]=dp[a[i].pr]+a[i].w if不选a[i] dp[i]=dp[i-1];

建立递推关系： dp[i]=max{dp[a[i].pr]+a[i].w,dp[i-1]}

显然，这里用动归是非常好的

#include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef struct{ int start;//开始时间 int end;//结束时间 int w;//权重 int pr;//记录该活动开始前，最后结束的活动 }ACTIVITY; bool cmp(ACTIVITY& a,ACTIVITY& b){ return a.end < b.end; } int find(ACTIVITY a[],int k){ for (int i = k-1; i >= 0;i--){ if(a[i].end<=a[k].start){ return i; } } } int main(){ //预处理 int n; cin>>n; bool rec[n + 1];//记录是否选择 memset(rec, 0, sizeof(rec)); ACTIVITY a[n + 1]; for (int i = 1; i <= n;i++){ cin >> a[i].start >> a[i].end >> a[i].w; } sort(a + 1, a + n + 1, cmp); a[0].end = 0; for (int i = 1; i <= n;i++){ a[i].pr = find(a,i); } //初始化 int dp[n + 1]; dp[0] = 0; //动态规划 for (int i = 1; i <= n;i++){ if(dp[a[i].pr]+a[i].w>dp[i-1]){ dp[i] = dp[a[i].pr] + a[i].w; rec[i] = 1; }else{ dp[i] = dp[i - 1]; rec[i] = 0; } } //输出方案 int i = n; while(i>0){ if(rec[i]){ cout << i << " "; i = a[i].pr;//排除时间重叠 }else{ i--; } } cout << endl; return 0; } //这里注意一下，追踪数组rec记录的是该活动是否被选过，但时间重叠的这里没有排除，比如: //选择活动1是必然的(rec[1]=1)，但是虽然活动2和1时间冲突，但2权重大，所以2也被选了（rec[2]=1），但最终结果，2和1只能选一个。 //因此，方案输出时，不能只考虑rec[i]是否为1，要从后往前依次考虑时间重叠问题