精华内容
下载资源
问答
  • 2021-07-22 11:05:16

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

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

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

    实验步骤
    ①首先计算每种物品单位重量的价值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;
    }
    
    
    更多相关内容
  • 贪心算法求解背包问题 #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;...
  • C++应用贪心算法求解背包问题.docx
  • C++应用贪心算法求解背包问题,可用于算法课程设计答辩。
  • 贪心算法求解背包问题

    千次阅读 2021-05-26 13:21:00
    用贪心策略设计并实现一个贪心算法求解背包问题。 2.算法基本思想 每次找未装包的物品中单位重量价值最大的物品装包,装包的同时也要考虑到背包的剩余容量。 3.主要数据结构及其作用 动态数组:存储数据 4.测试...

    1.实验要求
    用贪心策略设计并实现一个贪心算法,求解背包问题。

    2.算法基本思想
    每次找未装包的物品中单位重量价值最大的物品装包,装包的同时也要考虑到背包的剩余容量。

    3.主要数据结构及其作用
    动态数组:存储数据

    4.测试用例
    测试用例
    5.实验结果截图
    实验结果1
    测试用例1
    测试用例2
    测试用例2
    测试用例3
    测试用例3
    6.代码实现

    #include<iostream>
    using namespace std;
    int main(){
    	int c,n;
    	cout<<"请输入背包的容量c:";
    	cin>>c;
    	cout<<endl;
    	cout<<"请输入物品的件数n:";
    	cin>>n;
    	cout<<endl;
    	int *w=new int [n];
    	int *v=new int [n];
    	float *p=new float[n];
    	bool *s=new bool[n];
    	cout<<"请输入每件物品的重量w[i]:";
    	for(int i=0;i<n;i++)
    		cin>>w[i];
    	cout<<endl;
    	cout<<"请输入每件物品的价值v[i]:";
    	for(int i=0;i<n;i++){
    		cin>>v[i];
    		p[i]=v[i]*1.0/w[i];
    		s[i]=true; //没装
    	}
    	cout<<endl;
    	float temp_p=0;
    	int temp_i=0;
    	float value=0;
    	while(c>0){
    		temp_p=0;
    		for(int i=0;i<n;i++)
    			if(s[i]&&p[i]>temp_p)//找到未装到背包中的单位重量价值最大值
    			{
    				temp_p=p[i];
    				temp_i=i;
    			}
    		s[temp_i]=false; //已经装入
    		if(c>=w[temp_i]){
    			c-=w[temp_i];
    			value+=v[temp_i];
    		}
    		else
    		{
    			value+=c*p[temp_i];
    			w[temp_i]=c;
    			c=0;
    		}
    	}
    	for(int i=0;i<n;i++)
    		if(!s[i])
    			cout<<"装入总价值为"<<v[i]<<"的物品的总重量为:"<<w[i]<<endl;
    		cout<<"最大的总价值为:"<<value<<endl;
    }
    
    展开全文
  • 利用贪心算法求解背包问题【python实现】 求解思路:求出各物品价值与体积之比,由高到低排序,尽可能放价值比高的物品。 """" author:xuke 实现功能:利用贪心算法求解背包问题 """ #各物品的体积列表 v = [] #...

    利用贪心算法求解背包问题【python实现】

    求解思路:求出各物品价值与体积之比,由高到低排序,尽可能放价值比高的物品。

    """"
        author:xuke
        实现功能:利用贪心算法求解背包问题
    """
    
    #各物品的体积列表
    v = []
    #各物品的价值列表
    val = []
    #各物品编号
    num = []
    #各物品价格/体重
    v_val = []
    #输入背包体积
    VS = eval(input("背包体积为:"))
    #输入物品种类数
    S = eval(input("物品种类数目为:"))
    #输入各物品信息
    for i in range(S):
        num.append(input("第{}类物品的编号为:".format(i+1)))
        v.append(eval(input("第{}类物品的体积为:".format(i + 1))))
        val.append(eval(input("第{}类物品的价值为:".format(i + 1))))
    
    print("各物品信息:")
    print("编号:{}".format(num))
    print("体积:{}".format(v))
    print("价值:{}".format(val))
    #计算价格与体重之比
    for i in range(S):
        v_val.append(val[i]/v[i])
    #排序
    for i in range(S):
        for j in range(i+1,S):
            if v_val[i] < v_val[j]:
                v_val[i],v_val[j] = v_val[j],v_val[i]
                v[i],v[j] = v[j],v[i]
                val[i],val[j] = val[j],val[i]
                num[i],num[j] = num[j],num[i]
    
    print("编号:{}".format(num))
    print("体积:{}".format(v))
    print("价值:{}".format(val))
    
    #不可分割物品
    #当前背包占用体积
    v1_now = 0
    #当前背包内价值
    val1_now = 0
    
    print("背包内加入的物品编号有:",end='')
    for i in range(S):
        if (v[i] + v1_now) <= VS:
            v1_now +=v[i]
            val1_now += val[i]
            print(num[i],end='')
        else:
            break
    print()
    #背包占用体积为
    print("背包体积:{}".format(v1_now))
    print("背包价值:{}".format(val1_now))
    
    #可分割物品
    #当前背包占用体积
    v2_now = 0
    #当前背包内价值
    val2_now = 0
    
    print("背包内加入的物品编号有:",end='')
    for i in range(S):
        if (v[i] + v2_now) <= VS:
            v2_now +=v[i]
            val2_now += val[i]
            print(num[i],end='')
        elif v2_now < VS:
            last = VS - v2_now
            val2_now +=val[i]*(last/v[i])
            v2_now = VS
            print(num[i],end='')
        elif v2_now == VS:
            break
    
    print()
    print("背包价值:{}".format(val2_now))
    展开全文
  • 码: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都是有优化程序的作用的;

    展开全文
  • 实验五贪心算法求解背包问题 实验内容 应用贪心算法求解离散背包问题分析时间复杂度 有一个承重为W的背包和n个物品它们各自的重量和价值分别是wi和vi1设 求这些物品中最有价值的一个子集如果每次选择某一个物品的...
  • 贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。应用:1:该问题可以通过“局部寻优”逐步过渡到“整体最优”,这是贪心选择性质与“动态规划”的主要差别。2:最优子结构性质:某个...
  • 贪心算法解决背包问题

    千次阅读 2022-04-12 17:21:12
    贪心算法实现背包问题求解。背包容量为20;最优解为装入背包的物品价值总和最大。 基本思想: 计算所有物品的性价比 按物品性价比从高到低装入,只有当高一级的性价比物品全部装入后,才会装入下一级的性...
  • 贪心算法求解普通背包问题的C++代码2019年3月6日 125次阅读 来源: 贪心算法#include#define M 100void display(int &n,double &C,double s[M],double p[M]){int i;cout<cin>>n;cout<cout<...
  • 贪心算法 背包问题 c语言 绝对无误 运行成功
  • 贪心求解背包问题。 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 用到的思想—贪心法 博主用到的环境:Win7, CodeBlocks等。 一、代码 #include<...
  • 背包问题贪心算法求解

    万次阅读 多人点赞 2019-10-06 22:14:11
    题目 有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。...这2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,而0-1背包问题却不能用贪心算法求解。 求解步骤 用...
  • 本文实例讲述了Python基于贪心算法解决背包问题。分享给大家供大家参考,具体如下: 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出...
  • 贪心算法背包问题

    千次阅读 2021-08-24 01:01:30
    贪心算法背包问题背包问题是算法的经典问题,分为部分背包和0-1背包,主要区别如下:部分背包:某件物品是一堆,可以带走其一部分0-1背包:对于某件物品,要么被带走(选择了它),要么不被带走...
  • 给定n种物品和一个背包。物品i的重量为wi,其价值为vi,背包容量为c。问应该如何选择装入背包中的物品使得装入背包中的物品的总价值最大。
  • 针对传统的离散粒子群优化算法后期容易陷入局部收敛这一缺点,提出了一种新的离散...用改进的算法求解背包问题,通过与其他文 献中仿真实例的计算和结果比较,表明该算法在全局寻优能力和收敛性上都优于传统的粒子群算法。
  • 探究-贪心算法解决背包问题(Java实现)
  • 有一个背包容量150,有7个物品,只考虑重量,不考虑物体体积,尽可能往背包里装贵的东西,最多装多少呢? 这个问题还分了两种,一种是物体不能拆,也叫0-1背包,算出来是... * 背包问题 */ public class Backpack {

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,077
精华内容 3,230
关键字:

贪心算法求解背包问题

友情链接: UNIT--II.zip