-
2021-12-21 22:23:07
分析:背包问题用贪心算法解决,首先就是计算每个物品的性价比(价格/重量),然后进行排序,先装性价比高的物品再依次装入性价比第二、三......高的,如果背包剩余量小于物品的重量,则可以将物品进行拆分,将部分物品装进背包中。
代码如下:
#include<bits/stdc++.h> using namespace std; struct node { int w,v;//重量,价值 double p; }a[1005]; int cmp(node a,node b) { return a.p>b.p; } int main() { int n,c; double ans=0; cin>>n>>c; if(n==0 || c==0) return 0; for(int i=0;i<n;i++) cin>>a[i].v; for(int i=0;i<n;i++) cin>>a[i].w; for(int i=0;i<n;i++) a[i].p=(double)a[i].v/a[i].w;//物品的价值比上重量 sort(a,a+n,cmp); for(int i=0;i<n;i++) { if(a[i].w<=c) { ans+=a[i].v; c-=a[i].w; } else { ans+=a[i].p*c; break; } } cout<<ans; }
更多相关内容 -
部分背包问题证明贪心算法正确性
2021-01-30 12:16:04证明贪心算法的结构 第一步:符合贪心选择的特性(Greedy Choice Property) 我们需要证明我们的第一个选择(贪心选择 Greedy Choice,First Choice)包含在某些最优解中 第二步:符合归纳法结构(Inductive ...部分背包问题
证明贪心算法的结构
第一步:符合贪心选择的特性(Greedy Choice Property)
我们需要证明我们的第一个选择(贪心选择 Greedy Choice,First Choice)包含在某些最优解中
第二步:符合归纳法结构(Inductive Structure)
我们需要证明第一个选择(贪心选择)
之后,子问题
和原问题
还是同一类问题,意味着我们的选择不改变问题的结构,并且子问题
的解可以和第一个选择(贪心选择)
合并
第三步:最优子结构(Optimal Substructure)
如果我们可以最优的解决子问题
,我们可以将子问题
的解和贪心选择
得到原问题
的解
问题本身
输入:
个物品,每个物品
有自身的重量和价值
- 1个背包,背包最多可以存放重量为
的物品
前提:每个物品可以只取其中的一部分,比如拿0.5个某物品
输出:
- 在每个物品可以只取其中的一部分的前提下,使得背包内物品价值最大
定义我们的算法:
按照每个物品的密度
给物品进行升序排列,然后从密度最高的物品开始选,如果空间不够存放一整个物品,就能存放多少部分这个物品就存放多少部分(Best fit)
证明符合贪心选择的特性:
Claim:让物品
为最高密度的物品,假设这里存在一个最优解用到了
这么多重量的物品
证明:
让
为最优解,
- 如果
用到了
多的物品
,那么已经证明了我们的第一个选择(Greedy Choice,First Choice)包含在某些最优解中。
- 如果
没有用到
多的物品
,那么我么可以将背包中任意一部分和物品
进行交换,因为我们是按照物品密度排序,而且我们已经定义物品
为最高密度的物品,所以与物品
交换的物品必然比物品
的密度要小,所以等量交换后,我们得到的解
会比
更优,这个结论与和
为最优解的假设冲突,所以最优解
中必然含有
多的物品
。因此符合贪心选择的特性(Greedy Choice Property)。
证明符合归纳法结构(Inductive Structure)
Claim:在完成第一个选择(贪心选择)
之后,子问题
和原问题
还是同一类问题,意味着我们的选择不改变问题的结构,并且子问题
的解可以和第一个选择(贪心选择)
合并
证明:
- 子问题
含有除了物品
之外的所有物品,背包容量变成了
,因此物品
可以和子问题
的解合并。
证明最优子结构(Optimal Substructure)
Claim:定义
为原问题,
为在完成第一个选择(贪心选择)
之后的子问题,
为子问题
的最优解,那么
为原问题
的最优解
证明:
- 让
为贪心选择
(
是
)
- 那么
假设
不是最优解,有一个其他的最优解
,因为我们已经证明了算法符合贪心选择的特性,所以我们知道最优解
中一定含有贪心选择
- 那么
就应该是子问题
的解
- 所以
- 但是这与
为子问题
的最优解的定义产生冲突,所以
不可能不是最优解,因为
为原问题
的最优解。QED
-
Python基于贪心算法解决背包问题示例
2020-12-23 20:47:24本文实例讲述了Python基于贪心算法解决背包问题。分享给大家供大家参考,具体如下: 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出... -
greedy_哈夫曼编码_活动安排_背包问题_python_贪心算法_
2021-10-03 15:08:59Python编写的,利用贪心算法解决活动安排、哈夫曼编码、背包问题、最电路径、最优装载、最小生成树等问题 -
JS基于贪心算法解决背包问题示例
2020-10-18 23:22:04主要介绍了JS基于贪心算法解决背包问题,简单说明了贪心算法的概念、原理,并结合具体实例形式分析了JS使用贪心算法解决部分背包问题的具体操作技巧,需要的朋友可以参考下 -
贪心算法之背包问题
2018-10-31 17:03:09贪心问题中有很多典型的例子,此次背包问题,助大家理解该算法 -
阿里巴巴背包问题贪心算法
2021-01-20 13:33:04物品课分割的装载问题称为背包问题,物品不可分割的装载问题称为0-1背包问题。 #include #include using namespace std; //按性价比贪心策略 typedef struct three { double w; //重量 double v; //价值 double p... -
贪心算法解多重背包代码
2020-05-21 15:30:31使用贪心算法解决多重背包问题(物体可拆分)的具体C++代码 -
贪心算法求解背包问题C语言描述.doc
2020-11-02 10:25:14贪心算法求解背包问题 #include<stdio.h> #define maxnumber 20 typedef struct node { float w; float v; int i; }Object; float find(Object wp[],int n,float M) { float x[maxnumber]; int i; float maxprice=0;... -
背包问题 贪心算法实现
2014-06-27 22:30:34背包问题的贪心算法实现,简单易懂,初学者可参考 -
背包问题——贪心算法
2022-03-24 21:08:20问题描述: 假设山洞中有n种宝物,每种宝物...0-1背包问题详见01背包问题_Player_HA的博客-CSDN博客 数据结构及初始化,将n种宝物的重量和价值存储在结构体three(包含重量、价值、性价比3个成员)中,同时求出每种宝物问题描述:
假设山洞中有n种宝物,每种宝物有一定重量w和相应的价值v,毛驴运载能力有限,只能运走m重量的宝物,一种宝物只能拿一样,宝物可以分割。那么怎么才能使毛驴运走宝物的价值最大呢?
问题分析:
与0-1背包问题类似,所不同的是在选择物品装入背包时,物品可分割,因此可按性价比(价值/质量)排序选择不同的物品。
0-1背包问题详见01背包问题_Player_HA的博客-CSDN博客
数据结构及初始化,将n种宝物的重量和价值存储在结构体three(包含重量、价值、性价比3个成员)中,同时求出每种宝物的性价比也存储在结构体three中,将其按照性价比从高到低排序。采用sum来存储毛驴能够运走的最大价值,初始化为0。
例如:
代码:
#include<iostream> #include<algorithm> using namespace std; const int M = 100000; //背包结构体 struct three { double w;//weight double v;//value double p;//性价比 }S[M]; bool cmp(three a, three b)//添加比较规则 { return a.p > b.p; }//降序排性价比 int main() { int n;//n个物品 double m;//承载能力 cout << "输入物品数量和承载能力:" << endl; cin >> n >> m; cout << "输入每个宝物的重量和价值:" << endl; for (int i = 0; i < n; i++) { cin >> S[i].w >> S[i].v; S[i].p = S[i].v / S[i].w;//性价比 } sort(S, S + n, cmp);//调用库中的函数sort cmp为比较方法 double sum = 0.0;//表示贪心记录运走宝物的价值 int m1 = m; for (int i = 0; i < n; i++) { if (m > S[i].w) { m -= S[i].w; sum += S[i].v; } else { sum += S[i].p * m; break;//容器已经装满,跳出循环 } } cout << "装得的最大价值:" << sum << endl; cout << "装得的物品性价比:" << endl; for (int i = 1; i <=n; i++) { cout << "["<<i<<"]:" << S[i].p << endl; } }
-
数据结构与算法学习之路:背包问题的贪心算法和动态规划算法
2021-05-25 06:14:44二、解决方法:1、贪心算法:贪心算法基于的思想是每一次选择都作当前最好的选择,这样最后的结果虽然不一定是最优解,但是也不会比最优解差很多。举个例子说明可能好懂一些:一帮基友去聚餐,菜是一份一份上的,我...一、背包问题描述:
有N种物品和一个重量为M的背包,第i种物品的重量是w[i],价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包重量,且价值总和最大。
二、解决方法:
1、贪心算法:贪心算法基于的思想是每一次选择都作当前最好的选择,这样最后的结果虽然不一定是最优解,但是也不会比最优解差很多。
举个例子说明可能好懂一些:一帮基友去聚餐,菜是一份一份上的,我每一次夹菜都只夹牛肉/海鲜吃,可能到最后我吃的牛肉/海鲜很多,但不一定代表我吃掉的东西的总价值最高,但是相对来说价值也很高了~
换句话说,对于贪心算法,其核心在于设定一个标准让我们去贪。回到这个问题,这个标准就有三种设法了:1、价值最高的先装进背包;2、重量最低的先装进包;3、性价比(价值和重量的比值)最高的先装进背包。我在这里用的是第三种方法,用快排作了排序。
在装的过程中要注意的就是,当前物品能不能放进背包。这个是需要考虑的。因为背包问题也有好几种,如:0-1背包问题(每种物品只能拿一次)、完全背包问题(每种物品都能拿无限次)、多重背包问题(每种物品都有一定的数量可以拿)。所以在不同情况下贪心算法的一些细节设计也是不一样的,这个需要自己考虑。
2、动态规划算法:贯穿动态规划算法的就是状态和状态转移方程这两个东西,而要得到这两个东西需要我们把我们的问题分解为更小的子问题,通过分析子问题去获得。这个我在LIS问题上也讲过(数据结构与算法学习之路:LIS——最长递增序列的动态规划算法和二分思想算法)
那么回到我们这个问题,由于每次装东西进背包,我们只考虑能否装进,以及是否当前状态下的最优选择,也就是说,我们需要用背包的容量去设计一个数组,存储每一单位个容量的最大价值是多少,以此类推,获得背包容量下的最大价值是多少。这样说可能说不清楚,看看下面的代码吧~
三、代码:
1、贪心算法:
void Greedy_KnapSack(Greedy_BagPtr greedy_bags, float bagWeight){
float temp = bagWeight;
Quick_Sort(greedy_bags, 0, 9);
for (int i = 9; i >= 0; --i){
if (greedy_bags[i].weight <= temp){
temp -= greedy_bags[i].weight;
greedy_bags[i].resultWeight = 1;
}
else if (greedy_bags[i].weight > temp && temp > 0){
greedy_bags[i].resultWeight = temp / greedy_bags[i].weight;
temp = 0;
}
else if (temp < 0)
return;
}
}
2、动态规划算法:
int DP_KnapSack(DP_BagPtr dp_bags, int bagWeight){
int i, size = bagWeight + 1,currentMaxValue;
int *dp_bagweight = (int*)malloc(size*sizeof(int));
dp_bagweight[0] = 0;
for (i = 1; i < size; ++i){
currentMaxValue = 0;
if (i <= 9 && i > 0){
for (int j = 0; j < BAGSIZE; ++j){
if (dp_bags[j].weight == i && dp_bags[j].value > currentMaxValue)
currentMaxValue = dp_bags[j].value;
}
if ((dp_bagweight[i - 1] + 1) > currentMaxValue)
dp_bagweight[i] = dp_bagweight[i - 1] + 1;
else
dp_bagweight[i] = currentMaxValue;
}
else{
if ((dp_bagweight[i - 1] + 1) > (dp_bagweight[9] + dp_bagweight[i % 9]))
dp_bagweight[i] = dp_bagweight[i - 1] + 1;
else
dp_bagweight[i] = dp_bagweight[9] + dp_bagweight[i % 9];
}
}
return dp_bagweight[bagWeight];
}
3、可能有人会需要,在解决这个问题的情况下我修改的快排
void Quick_Sort(Greedy_BagPtr bags, int start, int end){
if (start < end){
int i = start, j = end;
Greedy_Bag temp = bags[start];
while (i < j){
while (i < j && bags[j].relativeValue >= temp.relativeValue)
--j;
if (i < j)
bags[i++] = bags[j];
while (i < j && bags[i].relativeValue < temp.relativeValue)
++i;
if (i < j)
bags[j--] = bags[i];
}
bags[i].value = temp.value;
bags[i].weight = temp.weight;
bags[i].resultWeight = temp.resultWeight;
bags[i].relativeValue = temp.relativeValue;
Quick_Sort(bags, start, i - 1);
Quick_Sort(bags, i + 1, end);
}
}
-
c语言背包问题_背包问题贪心算法_背包问题 贪心算法(13)
2021-05-24 03:54:35找一个图的所有m—着色方案procedure mcoloring(k)//这是图着色的一个递归回溯算法。图g用它的布尔邻接矩阵graPh(1:n,1:n)表示。它计算并打印出符合以下要求的全部解,把整数1,2,…,m分配给图中各... -
贪心算法解背包问题
2014-08-18 15:56:11利用贪心算法,计算出一个背包里面最多能装下多少东西, -
背包问题之贪心算法
2021-10-26 21:28:53经典的背包问题有两种: 1. 01背包问题-->01背包-动态规划_KING素清风的博客-CSDN博客 【01背包问题这里就不详细介绍了,感兴趣的可以看我的另一篇博客】 2.部分背包问题-->有一个背包,容量是C,有若干... -
贪心算法 背包问题 c语言
2013-06-18 11:27:37贪心算法 背包问题 c语言 绝对无误 运行成功 -
部分背包问题——贪心算法
2021-09-08 20:50:58部分背包问题: 输入:n个物品组成的集合O,每个物品有两个属性Vi和Pi,分别表示体积和价格 背包容量为C 输出:求解一个解决方案S={Xi|1<=i<=n,0<=Xi<=1},使得: 优化目标为max(Xi·Pi的总和) 约束... -
【Python实现背包问题的贪心算法】
2022-03-28 16:19:07Python实现背包问题的贪心算法 -
0-1背包问题贪心算法
2015-06-07 12:51:15算法课程的0-1背包问题贪心算法代码,含截图,经测试可用 -
背包问题,贪心算法实现(示例代码)
2021-05-24 03:08:40背包问题:有 N 件物品和一个承重为 W 的背包(也可定义为体积),每件物品的重量是 weight,价值是 value,求解将哪几件物品装入背包可使这些物品在重量总和不超过 backpack_weight 的情况下价值总和最大。... -
背包问题 贪心法——C语言代码
2020-05-23 15:45:22课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的 -
01背包问题的贪心算法.pdf
2012-12-01 10:21:4901背包问题的贪心算法,详细解析,令你很快懂的01背包问题中的贪心算法思想 -
背包问题的贪心算法.doc
2022-05-06 22:26:21背包问题的贪心算法.doc -
贪心算法-背包装载问题
2021-05-23 16:11:01贪心算法-背包装载问题 -
[算法]背包问题的经典算法和贪心算法解答,C语言实现
2021-05-21 09:01:27/*背包问题之经典解法和贪心算法*code cg*2008 12 24*调试环境TC ,devC++*/#include "stdio.h"#include "stdlib.h"#include "conio.h"#define N 5 /*定义需要放的物件数量*/#define PSIZE 150/*定义背包大小*/long ... -
0-1背包问题-贪心算法
2020-12-21 18:26:46今天用贪心算法给出背包问题的一种解,虽然贪心算法不一定是最优解,但是在数据量极大时,贪心算法可以快速获得接近最优解的答案packagetest;importjava.util.ArrayList;importjava.util.Collections;importjava.... -
贪心算法 部分背包问题
2015-12-19 15:06:53一个贪心算法的比较简单的程序,经运行是可以使用的 -
部分背包问题-贪心算法
2021-04-19 19:56:27部分背包问题-贪心算法 问题描述 有一个调制饮品比赛 ⚫参赛者拥有容量为 c ml的杯子,可任选不超过体积上限的饮料进行混合 ⚫ 调制饮品价格为各所使用饮料的价格之和,所得饮品价格之和最高者获胜 每种饮品有对应的...