精华内容
下载资源
问答
  • 贪心算法01背包
    2021-11-19 08:06:20
    package pack;
    
    import java.util.Arrays;
    import java.util.Scanner;
    /*
    * 代码潜在bug
    * 1.
    * 第46行,Need数组是float数组没有对进入的数组进行保留2位小数进行处理(虽然题中没说,但感觉是不安全的)
    * */
    public class Pack {
        public static void main(String[] args) {
            //读取控制台数据
            Scanner scanner = new Scanner(System.in);
            int G = scanner.nextInt();
            int n = scanner.nextInt();
    
            //变量定义
            int[] Weight = new int[n];//重量
            int[] Value = new int[n];//单物品总价值
            float[] Need = new float[n];//需要各物品的值,初始值为0
            int keyMax= 0; //最大单价数组下表
            float totalValue=0;//背包所带物品的最大价值
    
            //输入数据
            for(int i=0;i<n;i++){
                Weight[i]=scanner.nextInt();
            }
            for (int i=0;i<n;i++){
                Value[i] = scanner.nextInt();
            }
            //各物品单价(一斤多少钱)
            float Price[] = new float[n];
            for (int i=0;i<n;i++){
                Price[i] =(float) Value[i]/Weight[i];
            }
            //核心
            while (true){
                keyMax = FindMax(Price,n);//接收返回值
                if(Weight[keyMax]<G){//当单价最大的物品的总重量小于背包可容纳最大值时
                    G=G-Weight[keyMax];//修改背包容量最大值
                    Need[keyMax]=1;//将价值最大的物品全部放入背包
                    Price[keyMax]=0;//消除最大值
                    totalValue =(float) Value[keyMax]+totalValue;//增加背包总价值
                    continue;
                }
                if (Weight[keyMax]>G){//当单价最大的物品大于背包可容纳最大值时
                    Need[keyMax]=(float)G/Weight[keyMax];//算出放入背包多少该物品
                    totalValue =(float) Need[keyMax]*Value[keyMax] + totalValue;//增加背包总价值
                    G=0;//修改背包容量
                }
                if (G==0){
                    break;
                }
            }
            //结果输出
            System.out.println("各物品个取:"+Arrays.toString(Need));
            System.out.println("物品总价值:"+totalValue);
    
        }
        //找出Price(单价)最大的,返回下标
        static int FindMax(float[] Price,int n){
            float MAX=Price[0];
            int key = 0;
            for(int i=1;i<n;i++){
                if(Price[i]>MAX){
                    MAX=Price[i];
                    key=i;
                }
            }
            return key;
        }
    }
    

    更多相关内容
  • 贪心算法背包问题

    2018-10-31 17:03:09
    贪心问题中有很多典型的例子,此次背包问题,助大家理解该算法
  • 贪心算法01背包算法实验报告1.问题2.解析3.设计4.分析5.源码 实验报告 课程名称 《算法分析与设计》 实验名称 贪心算法01背包算法 1.问题 [描述算法问题,首选形式化方式(数学语言),其次才是非形式化方式...

    实验报告

    课程名称 《算法分析与设计》
    实验名称 贪心算法和01背包算法

    1.问题

    [描述算法问题,首选形式化方式(数学语言),其次才是非形式化方式(日常语言)]
    给你一个空间,告诉你这个空间的最大储存空间,告诉你一系列物品且知道每件物品的价值和占用空间,每件物品只能取一遍,问这个这个存储空间存放的东西数量最大是多少
    在这里插入图片描述

    2.解析

    [问题的理解和推导,可用电子版直接在此编写,也可用纸笔推导,拍照嵌入本文档]
    思路:01背包(dp)
    dp[j]就表示当下表为j的时候所能装载的最大数量.
    dp的状态转移方程dp[j] = max(dp[j], dp[j - w[i]] +1);(i从1~n 也就是所有的物品)
    思路:贪心
    想法:每次都选择最小的重量添加到其中
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3.设计

    [核心伪代码]
    1.贪心算法

    A = {1}
    J = 1
    For i = 2 to n do
    	If si > f
    	Then A = A{i}
    	J = i
    Return A
    

    2.01背包算法

    For i = 1 to n 
    	For j = n to w[i]
    		Dp[j] = max(dp[j], dp[j - w[i]] + 1)
    

    4.分析

    [算法复杂度推导]
    一、dp的时间复杂度复杂度O(nm)
    二、贪心的时间复杂度O(nlogn)

    5.源码

    github源码地址

    展开全文
  • 主要介绍了Python基于贪心算法解决背包问题,简单描述了贪心算法的概念、原理并结合实例形式分析了Python使用贪心算法解决背包问题的具体操作技巧,需要的朋友可以参考下
  • 主要介绍了JS基于贪心算法解决背包问题,简单说明了贪心算法的概念、原理,并结合具体实例形式分析了JS使用贪心算法解决部分背包问题的具体操作技巧,需要的朋友可以参考下
  • 贪心算法实现背包问题 集SSH框架,android,行业资讯,数据库,web开发,设计模式希望大家一起分享
  • 贪心算法求解背包问题

    千次阅读 2021-07-22 11:05:16
    ②然后根据贪心算法,将尽可能多的单位重量价值最高的物品装入背包,若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品尽可能多地装入背包。 ③按照以上策略,一直进行下去,...

    实验名称
    用贪心算法求解背包问题。

    实验目的
    通过上机实验,用贪心算法求解背包问题。

    实验原理
    使用贪心算法,根据不同的输入用例,能准确的输出最优值,并计算出程序运行所需要的时间。

    实验步骤
    ①首先计算每种物品单位重量的价值vi/wi,按单位价值重量进行升序排序
    ②然后根据贪心算法,将尽可能多的单位重量价值最高的物品装入背包,若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品尽可能多地装入背包。
    ③按照以上策略,一直进行下去,知道背包装满为止

    时间复杂度分析
    该算法具体实现中们主要的计算时间在于调用sort函数,因此算法的时间复杂度为:O(nlogn)。

    实验心得
    通过这次实验,我回顾了贪心算法。

    #include<iostream>
    #include<fstream>
    #include<windows.h> 
    #include<time.h>
    #include<stdlib.h> 
    #include<algorithm>
    using namespace std; 
    struct Goods
    {
        int weight;
        int value;
        float P;//权重=价值/重量 
        float N;//物品装入背包的部分,如果全部装入则为1,装入一半为0.5 
    };
    bool compare (Goods &a,Goods &b)
    {
        return a.P>b.P;
    }
    void Greedy(Goods goods[],int n, int c)
    {
        for(int i=0; i<n; i++)
        {
            if(c>goods[i].weight)
            {
                c-=goods[i].weight;
                goods[i].N=1;//如果背包足够装下整个物品,该物品全部装入记为1 
            }
            else if(c>0)
    		{//如果背包不足以装下整个物品,就装入物品的一部分 
                goods[i].N=c/(goods[i].weight*1.0);//计算物品装入背包的部分
                c=0; 
            }
        }
    }
    void creatrand(int m) 
    {
    	ofstream f_out;
    	f_out.open("input.txt", ios::out);
    	srand(time(NULL));
    	int r,s;
    	for ( int i = 0; i < m; i++)
    	 {
    		r =rand()%(10-1)+1;
    		s = rand()%(10-1)+1;
    		f_out << r << " "<<s<<endl;
    	}
        f_out.close();
    }
    int main()
    {
        int n,v;//n物品的数量,v背包的容量 
        float total_value=0;
        float total_weight=0;
        ofstream f_out;
        f_out.open("output.txt");
        ifstream f_in("input.txt"); 
        cout<<"请输入背包的容量:"<<endl;
        cin>>v;
        cout<<"请输入物品的数量:"<<endl;
        cin>>n;
        Goods goods[n];
        creatrand(n);
        cout<<"请分别输入物品的重量和价值:"<<endl;
        for(int i=0; i<n; i++)
        {   f_in>>goods[i].weight>>goods[i].value;//输入重量和价值 
            cout<< goods[i].weight<<" "<<goods[i].value<<endl;
            goods[i].P=goods[i].value/(goods[i].weight*1.0);
            goods[i].N=0;//N置0
        }
         LARGE_INTEGER time,time0,time1,time2;
    	QueryPerformanceFrequency(&time);
    	QueryPerformanceCounter(&time0);
        sort (goods,goods+n,compare);
        Greedy(goods,n,v);
         QueryPerformanceCounter(&time1);
        for(int i=0;i<n;i++)
        {   if(goods[i].N==0.0)break;
            total_value+=(goods[i].value*goods[i].N);//装入背包的物品总价值
            total_weight+=(goods[i].weight*goods[i].N);//装入背包的物品总重量
            f_out<<"weight: "<<goods[i].weight<<"  "<<"value: "<<goods[i].value
    		<<"  the part of goods: "<<goods[i].N<<endl;//输出装入背包的物品信息
    		cout<<"weight: "<<goods[i].weight<<"  "<<"value: "<<goods[i].value
    		<<"  the part of goods: "<<goods[i].N<<endl;//输出装入背包的物品信息
        }
        cout<<"背包的容量为: "<<v<<endl;//输出背包容量
        cout<<"装入背包中的物品的总重量为: "<<total_weight<<endl;//输出装入物品的总重量
        cout<<"装入背包中的物品的总价值为: "<<total_value<<endl;//输出装入物品的总价值
        f_out<<"背包的容量为: "<<v<<endl;//输出背包容量
        f_out<<"装入背包中的物品的总重量为: "<<total_weight<<endl;//输出装入物品的总重量
        f_out<<"装入背包中的物品的总价值为: "<<total_value<<endl;//输出装入物品的总价值
        f_out<<"时间为:"<<1000.0*(time1.QuadPart-time0.QuadPart)/time.QuadPart<<"ms"<<endl;
        cout<<"时间为:"<<1000.0*(time1.QuadPart-time0.QuadPart)/time.QuadPart<<"ms"<<endl;
        return 0;
    }
    
    
    展开全文
  • 一个贪心算法的比较简单的程序,经运行是可以使用的
  • C++应用贪心算法求解背包问题.docx
  • 背包问题 贪心法.cpp.rar,背包问题 贪心法.cpp
  • 码:w38a 算法分析与设计第 2 次实验 ... 贪心算法求解背包问题 实验目的 通过上机实验,要求掌握贪心算法的问题描述、算法设计思想、程序设计。 ...

    代码链接:pan.baidu.com/s/1rIugypf7lhUTfwdAG0Gv_w 
    码:w38a 

    算法分析与设计

    时间

    2020.4.22

    实验名称

    贪心算法求解背包问题

    实验目的

    通过上机实验,要求掌握贪心算法的问题描述、算法设计思想、程序设计。

    实验原理

    利用贪心法求解背包问题,并计算出程序运行所需要的时间。给定任意几组数据,利用贪心法求解背包问题的思想,选好物品使得背包价值最大。

    实验步骤

    问题分析

    形式化描述:给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量A=(x1,x2,…,xn), 0<=xi<=1(0~1表示取物品的某一部分),1<=i<=n,使得 ∑ wixi≤c(物品的重量和小于背包总容量)而且∑ vixi达到最大值;

    算法思想

    将物品按照单位重量价值进行排序(从大到小),将尽可能多的单位重量价值最高的物品装入背包,若将这种物品全部装入背包后,背包还有多余容量,则选择单位重量价值次高的并尽可能多地装入背包。如果最后一件物品无法全部装入,则计算可以装入的比例,然后按比例装入。

    算法步骤

    ①编写数据生成程序,随机生成三种规模输入文件

    ②将文件中数据读入w、v数组;

    ③对v[i]/w[i]进行从大到小排序;

    ④遍历排序好的序列,如果能将i物品全部放入背包则全部放入,直到遇到一个物品i的重量大于剩余容量,则将剩余容量的物品i放入背包,遍历结束;

    关键代码

    关键代码(带注释)

    1. 定义结构体保存第i个物品的标号i和它的单位重量的价值;

    定义结构体的目的是在对单位重量的价值进行排序后可以得到排序后的物品的标号;

    2. sort函数所需的第三个参数

    直接对每个物品的结构体进行排序(不改变w、v数组);

    3. 贪心算法求解函数(核心)

    x数组保存了含有物品标号与单价的结构体,首先将该结构体进行排序;

    接着从排序后的结构体的第一个物品进行遍历,做如下处理,直到背包塞满:

    如果物品i可以全部放入则直接加上v[x[i].id](第x[i].id个物品的价值),否则只放入物品的一部分令背包装满即可;

    4. 读取文件

     

    在进行输入的同时计算出物品单位重量价值;

    生成数据文件的方法与测试时间的方法与实验一相同;

    测试结果

    运行结果截图及分析

    例题输入输出文件:

     

    运行结果正确;

    三种规模的数据输入对比

    三种规模分别为:10、100、10000;

    这种算法的输入数据与输出结果都可以是浮点数;

    三种数据规模所需运行时间因为机器因素没有明显的呈现出nlogn的增长趋势,但是在数据规模增到10000时时间有明显的增加;

    时间复杂度分析

    排序算法(快速排序)的时间复杂度为O(nlogn),后面进行的贪心选择算法就算把数组全部遍历时间复杂度也只有O(n),因此排序算法是这个问题的关键算法,整个问题的时间复杂度为O(nlogn);

    实验心得

    通过这次实验,我回顾了贪心算法的基本原理,通过编程解题让我更加熟悉了这个算法的用法和优点。

    定义结构体是为了确保在对均值排序后能够通过结构体中的id查到对应单价的w、v,这也可以通过数组来实现;这种对应的关系是一种解题的小技巧,与第一个实验0-1背包问题中的jmax都是有优化程序的作用的;

    展开全文
  • 贪心算法-背包装载问题
  • c++—0/1背包问题--贪心算法(详解)

    千次阅读 2022-05-12 22:26:40
    贪心算法的基本思想 •贪心算法的特点是每个阶段所作的选择都是局部最优的,它期望通过所作的局部最优选择产生出一个全局最优解。 贪心与动态规划:与动态规划不同的是,贪心是鼠目寸光;动态规划是统揽全局。 ...
  • 实验三、 0-1 背包问题(贪心算法)实验代码:#includeint max(int a,int b){if(a>b)return a;elsereturn b;}void Knapsack(int *v,int *w,int *x,int c,int n, int m[8][100]){int i,j;for(j=0;j{if(jm[n][j]=0;...
  • 贪心算法解决背包问题

    千次阅读 2022-04-12 17:21:12
    贪心算法实现背包问题的求解。背包容量为20;最优解为装入背包的物品价值总和最大。 基本思想: 计算所有物品的性价比 按物品性价比从高到低装入,只有当高一级的性价比物品全部装入后,才会装入下一级的性...
  • 贪心算法 背包问题 c语言 绝对无误 运行成功
  • (Java)贪心算法解决01背包问题

    千次阅读 2018-11-01 21:48:08
    问题描述如下: 给定n种物品和一个背包。...经典的背包问题,这次选用贪心算法来解决 代码如下: package TXSF; import java.util.Scanner; public class BAG { public static void main(String a...
  • Python编写的,利用贪心算法解决活动安排、哈夫曼编码、背包问题、最电路径、最优装载、最小生成树等问题
  • 贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。应用:1:该问题可以通过“局部寻优”逐步过渡到“整体最优”,这是贪心选择性质与“动态规划”的主要差别。2:最优子结构性质:某个...
  • 01背包贪心算法前言合并区间最后一块石头的重量 前言 昨天在做力扣探索的时候遇到了两道数组题,看到题目的时候就感觉不知道如何下手。 苦思冥想一番,最后去偷看了答案,发现是贪心算法01背包。 因为之前听说...
  • 01背包问题的贪心算法.pdf 算法设计的重点 期末必考
  • 贪心算法求解背包问题 #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;...
  • 20 组员: 王丹 魏蕾 魏晓卡 李丹 背包问题的贪心算法 * 1 问题描述 内容提要 2 3 实验及结果 4 实验总结 算法思想及分析 * 已知有n种物品和一个可容纳c重量的背包每种物品i的重量为wi假定物品i的一部分放入背包会...
  • 贪心算法解决0-1背包问题,基础算法实现,可以运行
  • 01背包问题

    2014-05-23 13:48:02
    动态规划 01背包问题 POJ3624可以AC
  • 设有编号1、2、... 、n的n个物品,它们的重量分别为w1、w2、... 、wn,价值分别为v1、v2、... vn,其中wi、vi(1)均为正数。有一个背包可以携带的...与0/1背包问题的区别是,这里的每一个物品可以取一部分装入背包
  • 用3种方法求解0-1背包问题(贪心算法、动态规划、分支限界法),获得精确最优解或近似最优解均可。 通过一个规模较大的实例比较不同方法的求解速度,分析不同算法的时间复杂度,并分析是否能获得最优解。 实验结果...

空空如也

空空如也

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

贪心算法01背包