背包（贪心策略）
背包问题本色上即转载问题，一般为在一定前提限制规模内请求咱们追求最好的装载方式获取最好的利益。所以普通的背包问题咱们可以通过贪心算法来追求最好收益。
咱们通过一个大家都耳熟能详的故事来讲明贪心算法在普通背包问题中的利用。咱们要讲的就是“阿里巴巴以及四十大盗”的故事。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
有一天，阿里巴巴赶着毛驴上山砍柴。下山的时候，远远看见一股尘烟，洋溢着直上天空，朝他卷来。凑近以后，他才看清是一对人马，他们一共四十人，个个身强力壮、行为麻利。一个首级样子的人背着繁重的鞍袋，从丛林中走到一个巨石前，喃喃说道：“芝麻开门”，神奇的事情产生了，大石前骤然呈现一道宽敞的道路，于是匪徒们鱼贯而入。阿里巴巴待在树上察看着，直到他们走得无影无踪后，才从树上下来。他大声喊道：“芝麻开门！”，洞门当即打开，他谨慎翼翼地走进去，一下惊呆了！岩穴里堆满了金银珠宝。阿里巴巴想让乡亲们开开眼界，见识一下宝物，他想一个宝物拿一个，如果过重就用凿子凿开，但毛驴的装载能力是有限的，怎么样才能用驴子运走最大价值的财宝分给穷人呢？文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
问题分析文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
假定岩穴中有n种宝物，每一种宝物有一定重量w以及相应的价值v，毛驴运载能力有限，只能运走m重量的宝物，一种宝物只能拿同样，无非宝物是可以分割的。那么如何才能使得毛驴运走的宝物价值最大呢？文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
对于需要取得价值最大化的问题，咱们可以尝试贪心策略：文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
- 每一次挑拣价值最大化的宝物装入背包，得到的结果是不是最优？
- 每一次挑拣重量最小的宝物装入，能否得到最优解？
- 每一次挑拣单位重量价值最大的宝物，能否价值最高？
想想，如果选价值最大的宝物，但重量无比大，是不行的，由于装载能力有限，所以策略1不适合；如果选重量小的宝物，但可能价值也很小，所以也不能在总重限制的情况下保证价值最大，所以策略2也不适合；而策略3每一次选择单位重量价值最大的，也就是性价比（价值/重量）最高的宝物，如果可以到达运载重量m，那么总价值一定是最大的。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
宝物清单文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
样例文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
输入文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
第一行是宝物数量n以及最大装载能力m，以后n+1行分别是每一个宝物的重量w以及价值v文章源自微观生活（93wg.com）微观生活-https://93wg.com/5740.html
10 30
4 3
2 8
9 18
5 6
5 8
8 20
5 5
4 6
5 7
5 15输出
一行，表示装载的最大价值
70.5示例代码
include <cstdio>
include <iostream>
include <algorithm>
#include <cmath>using namespace std;
// 宝物属性的结构体
struct Node{
double w; //重量
double v; // 价值
double p; // 性价比
}nodes[10];int n; // 宝物数量
double m; // 背包载重double dp[100][100]; // 动态计划的表格
int cmp
{
return a.p > b.p;
}int main
{
cin >> n >> m;
for
{
double w,v;
cin >> w >> v;
nodes[i].w = w;
nodes[i].v = v;
nodes[i].p = v / w;
}
sort; // 将宝物按性价比排序。其实是否排序其实不影响结果// 状况转移方程的实现
for // 行，不同的宝物
{
for // 列，不同容量的背包
{
if // 第一个宝物
{
if
{
dp[i][j] = nodes[i].v;
}
}
else
{dp[i][j] = dp[i-1][j];
int col = j - nodes[i].w; // 隐含了数据类型转换
if
continue;
if
{
dp[i][j] = nodes[i].v + dp[i-1][col];
}}
}
}
int c = ceil;
cout << dp[n-1][c] << endl;
return 0;
}以上就是微观生活（93wg.com）关于“算法学习之从背包（贪心策略）到0-1背包（动态计划）”的详细内容，希望对大家有所帮助！
评论