精华内容
下载资源
问答
  • 分数背包问题——贪心算法
    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)

    我们需要证明第一个选择(贪心选择)\widehat{c}之后,子问题P'和原问题P还是同一类问题,意味着我们的选择不改变问题的结构,并且子问题P'的解可以和第一个选择(贪心选择)\widehat{c}合并

     

    第三步:最优子结构(Optimal Substructure)

    如果我们可以最优的解决子问题P',我们可以将子问题P'的解和贪心选择\widehat{c}得到原问题P的解

    问题本身

    输入:

    • n个物品,每个物品i有自身的重量和价值(w_i, v_i)
    • 1个背包,背包最多可以存放重量为M的物品

    前提:每个物品可以只取其中的一部分,比如拿0.5个某物品i

    输出:

    • 在每个物品可以只取其中的一部分的前提下,使得背包内物品价值最大

    定义我们的算法:

    按照每个物品的密度d_i= \frac{v_i}{w_i}给物品进行升序排列,然后从密度最高的物品开始选,如果空间不够存放一整个物品,就能存放多少部分这个物品就存放多少部分(Best fit)

    证明符合贪心选择的特性:

    Claim:让物品i^*为最高密度的物品,假设这里存在一个最优解用到了w=min(w_i,M)这么多重量的物品i^*

    证明:

    \pi ^*为最优解,

    • 如果\pi ^*用到了w=min(w_i,M)多的物品i^*,那么已经证明了我们的第一个选择(Greedy Choice,First Choice)包含在某些最优解中。
    • 如果\pi ^*没有用到w=min(w_i,M)多的物品i^*,那么我么可以将背包中任意一部分和物品i^*进行交换,因为我们是按照物品密度排序,而且我们已经定义物品i^*为最高密度的物品,所以与物品i^*交换的物品必然比物品i^*的密度要小,所以等量交换后,我们得到的解\pi '会比\pi ^*更优,这个结论与和\pi ^*为最优解的假设冲突,所以最优解\pi ^*中必然含有w=min(w_i,M)多的物品i^*。因此符合贪心选择的特性(Greedy Choice Property)。

    证明符合归纳法结构(Inductive Structure)

    Claim:在完成第一个选择(贪心选择)\widehat{c}之后,子问题P'和原问题P还是同一类问题,意味着我们的选择不改变问题的结构,并且子问题P'的解可以和第一个选择(贪心选择)\widehat{c}合并

    证明:

    • 子问题P'含有除了物品i^*之外的所有物品,背包容量变成了M'=M-w_{i}^*,因此物品i^*可以和子问题P'的解合并。

    证明最优子结构(Optimal Substructure)

    Claim:定义P为原问题,P'为在完成第一个选择(贪心选择)\widehat{c}之后的子问题,\pi '为子问题P'的最优解,那么\pi = \pi ' \cup {\widehat{c}}为原问题P的最优解

    证明:

    • v^*=w\cdot d_i为贪心选择\widehat{c}ww=min(w_i,M)
    • 那么value(\pi )=value(\pi ^{'})+v^*

    假设\pi不是最优解,有一个其他的最优解\pi^*,因为我们已经证明了算法符合贪心选择的特性,所以我们知道最优解\pi^*中一定含有贪心选择\widehat{c}

    • 那么\pi ^*-\widehat{c}就应该是子问题P'的解
    • 所以value(\pi ^*-\widehat{c})=value(\pi ^*)-v^*>value(\pi )-v^*=value(\pi ')
    • 但是这与\pi '为子问题P'的最优解的定义产生冲突,所以\pi = \pi ' \cup {\widehat{c}}不可能不是最优解,因为\pi = \pi ' \cup {\widehat{c}}为原问题P的最优解。QED

     

     

    展开全文
  • 本文实例讲述了Python基于贪心算法解决背包问题。分享给大家供大家参考,具体如下: 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出...
  • Python编写的,利用贪心算法解决活动安排、哈夫曼编码、背包问题、最电路径、最优装载、最小生成树等问题
  • 主要介绍了JS基于贪心算法解决背包问题,简单说明了贪心算法的概念、原理,并结合具体实例形式分析了JS使用贪心算法解决部分背包问题的具体操作技巧,需要的朋友可以参考下
  • 贪心算法背包问题

    2018-10-31 17:03:09
    贪心问题中有很多典型的例子,此次背包问题,助大家理解该算法
  • 物品课分割的装载问题称为背包问题,物品不可分割的装载问题称为0-1背包问题。 #include #include using namespace std; //按性价比贪心策略 typedef struct three { double w; //重量 double v; //价值 double p...
  • 使用贪心算法解决多重背包问题(物体可拆分)的具体C++代码
  • 贪心算法求解背包问题 #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;...
  • 背包问题贪心算法实现,简单易懂,初学者可参考
  • 背包问题——贪心算法

    千次阅读 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;
    	}
    	
    }
    

     

    展开全文
  • 二、解决方法: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);

    }

    }

    展开全文
  • 找一个图的所有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语言 绝对无误 运行成功
  • 部分背包问题: 输入:n个物品组成的集合O,每个物品有两个属性Vi和Pi,分别表示体积和价格 背包容量为C 输出:求解一个解决方案S={Xi|1<=i<=n,0<=Xi<=1},使得: 优化目标为max(Xi·Pi的总和) 约束...
  • Python实现背包问题贪心算法
  • 0-1背包问题贪心算法

    2015-06-07 12:51:15
    算法课程的0-1背包问题贪心算法代码,含截图,经测试可用
  • 背包问题贪心算法实现(示例代码)

    千次阅读 2021-05-24 03:08:40
    背包问题:有 N 件物品和一个承重为 W 的背包(也可定义为体积),每件物品的重量是 weight,价值是 value,求解将哪几件物品装入背包可使这些物品在重量总和不超过 backpack_weight 的情况下价值总和最大。...
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 01背包问题贪心算法,详细解析,令你很快懂的01背包问题中的贪心算法思想
  • 背包问题贪心算法.doc
  • 贪心算法-背包装载问题
  • /*背包问题之经典解法和贪心算法*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....
  • 一个贪心算法的比较简单的程序,经运行是可以使用的
  • 部分背包问题-贪心算法 问题描述 有一个调制饮品比赛 ⚫参赛者拥有容量为 c ml的杯子,可任选不超过体积上限的饮料进行混合 ⚫ 调制饮品价格为各所使用饮料的价格之和,所得饮品价格之和最高者获胜 每种饮品有对应的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,379
精华内容 6,151
关键字:

背包问题证明 贪心算法