算法设计和分析实验四：贪心算法求解背包问题

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==背包问题实验报告篇一：背包问题实验报告课程名称：任课教师：班级:201X姓名：实验报告算法设计与分析实验名称：解0-1背包问题王锦彪专业：计算机应用技术学号：11201X 严焱心完成日期： 201X年11月一、实验目的：掌握动态规划、贪心算法、回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对上述方法的理解。

二、实验内容及要求：1．要求分别用动态规划、贪心算法、回溯法和分支限界法求解0-1背包问题；2．要求显示结果。

三、实验环境和工具：操作系统：Windows7 开发工具：Eclipse3.7.1 jdk6 开发语言：Java四、实验问题描述：0/1背包问题:现有n种物品，对1<=i<=n，第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数C，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过C且总价值尽量大。

动态规划算法描述:根据问题描述，可以将其转化为如下的约束条件和目标函数：nmax?vixi?n??wixi?C?i?1?x?{0,1}(1?i?n)?i寻找一个满足约束条件，并使目标函数式达到最大的解向量nX?(x1,x2,x3,......,xn)wixi，使得?i?1?C，而且?vixii?1n达到最大。

0-1背包问题具有最优子结构性质。

假设(x1,x2,x3,......,xn)是所给的问题的一个最优解，则(x2,x3,......,xn)是下面问题的一个最优解：?n??wixi?C?w1x1max?i?2?x?{0,1}(2?i?n)?i如果不是的话，设(y?vixi。

i?2nn2,y3,......,yn)是这个问题的一个最优解，则?viyi??vixi，且w1x1 i?2i?2n??wiyii?2?C。

实验项目名称：贪心算法求连续背包问题一、实验目的：明确连续背包问题的概念；利用贪心算法解决连连续续背包问题；并通过本例熟悉贪心算法在程序设计中的应用方法。

二、实验原理： 贪心算法原理：在贪婪算法（greedy method ）中采用逐步构造最优解的方法。

在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。

决策一旦作出，就不可再更改。

作出贪婪决策的依据称为贪婪准则（greedy criterion ）。

三、实验内容与步骤：贪心算法求连续背包问题问题描述：已知n 个物体和1个背包，其中物体i 有重量w i 和价值v i ，背包承重量为W 。

求一装载方案，要求在不超过背包负重的前提下，背包中装入的物品价值最大。

很明显，如果1ni i w W =≤∑，则最优解就是装入全部物体，因此下面假设1n i i w W =>∑。

注：连续背包问题中的物体可以任意分割，即部分装入背包。

分析：连续背包问题可形式化为如下模型：{}11max ..[0,1],1,,ni ii ni ii i x v x w W s t x i n ==⎧≤⎪⎨∈∈⎪⎩∑∑对于连续背包问题，可用贪心技术求得最优解。

贪心策略是单位重量价值高者优先。

例如：所给物体的重量和价值如下，则，程序可以得到如下结果：最大价值为163.0；所选各物体的数量为：1.0 1.0 1.0 0.8参考程序段如下//连续背包问题的贪心算法，最大单位重量价值优先//输入：各物体重量w 、价值v 和背包重量W ，已按v/w 降序排列#include<stdio.h>int knapsack(int n1,float w1[],float v1[],float W1){ int i; float weight; float x[10],s=0; for(i=1;i<=n1;i++) x[i]=0; weight=0; i=1;while(weight<W1) {if(weight+w1[i]<W1){x[i]=1;weight=weight+w1[i];}else{x[i]=(W1-weight)/w1[i];weight=W1;}i++;}for(i=1;i<=n1;i++) s=s+x[i]*v1[i];printf("背包所能容纳商品的最大价值为:%f\n",s);printf("所选择的商品的一个序列为：\n");for(i=1;i<=n1;i++)printf("%8.3f",x[i]);}void main(){int n,i,j;float w[10],v[10],W;clrscr();printf("输入商品数量n 和背包容量W:\n");scanf("%d,%f",&n,&W);printf("输入每件商品的重量,价值:\n");for(i=1;i<=n;i++)scanf("%f,%f",&w[i],&v[i]);knapsack(n,w,v,W);printf("\n");system("pause");}。

C++贪⼼算法实现部分背包问题问题描述：在部分背包问题中，可以不必拿⾛整个⼀件物品，⽽是可以拿⾛该物品的任意部分。

以此求得在限定背包总重量，从给定的物品中进⾏选择的情况下的最佳（总价值最⾼）的选择⽅案。

细节须知：分别输出到同⽂件夹下两个⽂本⽂件中，名称分别是：“backpack-object.txt”和“backpack-weight.txt”。

算法原理：先求出所有物品的单位重量价值并进⾏由⼤到⼩的排序。

其次从排序处于⾸位的物品开始选择直到⽆法完整装⼊背包的物品，将其部分装⼊背包以填满背包的总重量，从⽽求得价值最⾼的选择⽅案。

1 #include <cstdio>2 #include <iostream>3 #include <ctime>4 #include <windows.h>5 #include <algorithm>6 #include <fstream>7using namespace std;8struct object9{10int no;11double weight;12double value;13double average;14};15bool cmp(const object &x, const object &y)16{17return x.average > y.average;//从⼩到⼤排<，若要从⼤到⼩排则>18}19void greedySelector(int m,int W,int solution[],struct object object[]){20int i = 0,V = 0,j = 0;21while(object[i].weight < W)22 {23 solution[i] = 1;24 W = W - object[i].weight;25 V = V + object[i].value;26 i++;27 }28 V = V + (W/object[i].weight)*object[i].value;29 solution[i] = 1;30 cout << "The corresponding value of the optimal option is:" << V << endl;31/*for( i = 0; i < m; i++)32 {33 if(solution[i] == 1)34 {35 cout << object[i].no << endl;36 }37 }*/38}39int main(void)40{41 LARGE_INTEGER nFreq;42 LARGE_INTEGER nBeginTime;43 LARGE_INTEGER nEndTime;44 ofstream fout1;45 ofstream fout2;46 srand((unsigned int)time(NULL));47int m,i,j,t;48double W;49double cost;50 cout << "Please enter the number of times you want to run the program:";51 cin >> t;52 fout1.open("backpack-object.txt",ios::app);53if(!fout1){54 cerr<<"Can not open file 'backpack-object.txt' "<<endl;55return -1;56 }57 fout1.setf(ios_base::fixed,ios_base::floatfield); //防⽌输出的数字使⽤科学计数法58 fout2.open("backpack-weight.txt",ios::app);59if(!fout2){60 cerr<<"Can not open file 'backpack-weight.txt' "<<endl;61return -1;62 }63 fout2.setf(ios_base::fixed,ios_base::floatfield); //防⽌输出的数字使⽤科学计数法64for (j = 0;j < t;j++)65 {66 cout << "——————————————————The "<< j + 1 << "th test —————————————————"<<endl;67 m = 1 + rand()%100000; //物品个数68 W = 10 + rand()%100000; //背包总重量69 fout1 << m << ",";70 fout2 << (int)W << ",";71int solution[m];72object object[m];73for( i = 0;i < m;i++)74 {75object[i].no = i + 1;76object[i].value = 1 + rand()%10000;77object[i].weight = 1 + rand()%10000;78object[i].average = object[i].value/object[i].weight;79 }80 QueryPerformanceFrequency(&nFreq);81 QueryPerformanceCounter(&nBeginTime);82 sort(object,object + m,cmp);83 greedySelector(m,W,solution,object);84 QueryPerformanceCounter(&nEndTime);85 cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;86 fout1 << cost << endl;87 fout2 << cost << endl;88 cout << "The running time is:" << cost << " s" << endl;89 }90 fout1.close();91 fout2.close();92 cout << endl;93 cout << "Success!" << endl;94return0;95 }程序设计思路：① 数据结构：结构体中存储物品序号、物品的重量、物品的价值、物品的单位重量价值；② 利⽤C++⾃带的sort函数对结构体按照物品的单位重量价值进⾏降序排列；③ 从排序处于⾸位的物品开始选择直到⽆法完整装⼊背包的物品，将其部分装⼊背包以填满背包的总重量，从⽽求得价值最⾼的选择⽅案。

算法分析实验报告贪心法解决背包问题学生姓名：专业：班级：学号:指导教师：2017年6月12日目录一、实验题目 (2)二、实验目的 (2)三、实验要求 (2)四、实现过程 (3)1、实验设计： (3)2、调试分析 (5)3、运行结果： (6)4、实验总结： (6)五、参考文献 (6)一、实验题目贪心法解决背包问题二、实验目的1）以背包问题为例，掌握贪心法的基本设计策略。

2）熟练掌握各种贪心策略情况下的背包问题的算法并实现；其中：量度标准分别取：效益增量v、物品重量w、v/ w比值；3) 分析实验结果来验证理解贪心法中目标函数设计的重要性。

三、实验要求1.[问题描述]：给定n种物品和一个背包。

物品i的重量是Wi，其价值为Vi，背包的容量为C。

应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，但不可以重复装入。

2.[算法]：贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

当达到某算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：1）不能保证求得的最后解是最佳的；2）不能用来求最大或最小解问题；3）只能求满足某些约束条件的可行解的范围。

四、实现过程1、实验设计：1.用贪心法求解背包问题的关键是如何选定贪心策略，使得按照一定的顺序选择每个物品，并尽可能的装入背包，直至背包装满。

至少有三种看似合理的贪心策略：1）按物品价值v降序装包，因为这可以尽可能快的增加背包的总价值。

但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗太快，使得装入背包得物品个数减少，从而不能保证目标函数达到最大。

2）按物品重量w升序装包，因为这可以装入尽可能多的物品，从而增加背包总价值。

但是，虽然每一步选择使背包得容量消耗得慢了，但背包价值却没能保证迅速增长，从而不能保证目标函数达到最大。

贪婪法求解背包问题-CAL-FENGHAI.-(YICAI)-Company One1实验二贪婪法一、实验目的1)理解和掌握贪婪算法的基本思想；2)使用贪婪算法求解背包问题以及最小花费生成树问题。

二、方法原理贪心算法就是做出一系列选择，使原问题达到最优解。

在每一个决策点，都是做出当前看来的最优选择。

三、实验设备PC机一台，C语言、PASCAL语言、Matlab任选四、方法原理贪心算法就是做出一系列选择，使原问题达到最优解。

在每一个决策点，都是做出当前看来的最优选择。

五、实验内容1)利用贪婪法求如下背包问题的最优解：n=5,M=100,价值P={20,30,66,40,60 }，重量为w={10,20,30,40,50}。

六、实验要求1)认真分析题目的条件和要求，复习相关的理论知识，选择适当的解决方案和算法；2)编写上机实验程序，作好上机前的准备工作；3)上机调试程序，并试算各种方案，记录计算的结果（包括必要的中间结果）；4)分析和解释计算结果；5)按照要求书写实验报告；源代码：#include<stdio.h>#include<stdlib.h>#include<iostream>using namespace std;#define n 5#define M 100typedef struct {int s;float p;//价值float w;float t;//价值重量比float x;}OBJECT;OBJECT obj[n];void swap(float &x, float &y) {float t;t = x;x = y;y = t;}float divide_and_conquer(OBJECT obj[], int low, int high) { int k, i = low;float z = obj[low].t;for (k = low + 1; k <= high; k++) {if (obj[k].t>z) {i += 1;if (i != k)swap(obj[i], obj[k]);}}swap(obj[low], obj[i]);return i;}void quick_sort(OBJECT obj[], int low, int high) {int k;if (low < high) {k = divide_and_conquer(obj, low, high);quick_sort(obj, low, k - 1);quick_sort(obj, k + 1, high);}}void sort_recover(OBJECT obj[]) {int i, j,temp;for (i = 0; i < n-1; i++) {for (j = 0; j < n - 1 - i; j++) {if (obj[j].s > obj[j + 1].s)swap(obj[j], obj[j + 1]);}}}float knapsack_greedy(OBJECT obj[]) {int i;float m,r=0;for(i=0;i<n;i++){obj[i].t=obj[i].p/obj[i].w;obj[i].x = 0;}quick_sort(obj,0,4);m = M;printf(" 物体价值重量价值重量比结果\n");printf("=========================================\n");for (i = 0; i < n; i++) {if (obj[i].w <= m) {obj[i].x = 1;m -= obj[i].w;r += obj[i].p;}else {obj[i].x = m / obj[i].w;r += obj[i].x * obj[i].p;break;}}return r;}void main() {int i;float r;//float x[] = { 0 };float s[] = { 1,2,3,4,5 };float p[]={ 20,30,66,40,60 };float w[]={ 10,20,30,40,50 };for (i = 0; i < n; i++) {obj[i].s = s[i];obj[i].p = p[i];obj[i].w = w[i];}r = knapsack_greedy(obj);sort_recover(obj);for (i = 0; i < n; i++) {printf(" %d %2.0f %2.0f %2.1f %1.1f\n", obj[i].s, obj[i].p, obj[i].w, obj[i].t, obj[i].x);}printf("\n最大价值为：%f\n",r );printf("背包问题的解向量：X={");for (i = 0; i < n; i++) {printf("%1.1f",obj[i].x);if(i<4)printf(",");}printf("}");system("pause");}结果：。

matlab中贪婪算法求解背包问题的研究与应用背包问题是一种特殊的最优化问题，常见于组合优化中。

在一般情况下，它要求从多种物品中挑选出某种数量的物品，并在总体质量限制下，达到总价值最优化。

背包问题最早由著名的十字军和维特根斯坦于末世纪四十年代被首先提出，他们认为它可以用来解决在野外战斗期间士兵装备配置问题。

在现代，当我们一定时间限制和资源限制的情况下做出最佳选择时，背包问题都会被广泛应用。

同时，它也被用来解决货币准备、电子商务中的物品搭配和货箱装箱等问题。

二、婪算法求解背包问题贪婪算法是一种能够有效解决搜索问题的算法，它总是在当前可行解中选择最优解。

这种算法的贪婪特性会让它比较容易实现，同时它也可以改善大多数最优时间复杂度和空间复杂度。

贪婪算法可以用来解决背包问题。

通过贪婪的决策选择，使得背包中的物品价值最大化。

贪婪算法的计算步骤如下：（1）根据背包容量，按比例选择价值较大且重量较轻的物品；（2）依次将价值最大的物品加入背包，直至规定重量到达为止；（3）检查最终获得的所有物品，保证它们尽可能满足重量限制。

三、lab中贪婪算法求解背包问题对于资源约束来说，lab中贪婪算法可以用来解决最优解问题。

lab中的贪婪算法可以用来求解背包问题，可以提高效率，提高求解的背包问题的精确度。

首先，可以将背包问题转化成一个更容易理解的数学模型：约束条件：质量：W=∑wi价值：V=∑xi其中，W为背包的总质量，V为背包的总价值，wi为第i个物品的质量，xi为第i个物品的价值。

设计算法：（1）根据约束条件取出有效物品，并且计算出每个物品的价值和质量比值；（2）按从大到小的价值比值顺序选择有效物品，并继续计算总的质量和价值；（3）当背包质量达到预定的容量时，停止选择，输出最终获得的最佳物品组合。

四、贪婪算法求解背包问题的实际应用贪婪算法求解背包问题在资源优化中有着很大的应用前景。

它可以用于供应链管理、资本规划、生产计划等领域，提高企业绩效，降低企业花销，从而改善企业生产力。

使⽤JAVA实现算法——贪⼼算法解决背包问题解释等全部在代码中，⾃⼰跑了下，是没问题的package BasePart;import java.io.BufferedReader;import java.io.FileInputStream;import java.io.IOException;import java.io.InputStreamReader;/*** 使⽤贪⼼算法解决背包问题* 背包问题：* 旅⾏者有背包容量m公⽄* 现在有重量W1,W2,W3,W4....Wn* 对应的价值V1,V2,V3,V4....Vn* 运⾏重复携带，欲求得最⼤价值* 贪⼼算法：求得最好的选择，但是贪⼼算法不是对于所有的问题都得到整体最优解* 贪⼼算法基本思路：* 1.建⽴数学模型来描述问题* 2.把求解问题分成若⼲个⼦问题* 3.对于每⼀个⾃问题求得局部最优解* 4.把⼦问题的解局部最优解合成原来解问题的⼀个解* 贪⼼算法的实现过程：* 从⼀个初始解出发* while-do朝总⽬标前进* 求出可⾏解的⼀个解元素* 由所有解元素组成合成问题的⼀个可⾏解*/public class Greedy {/*解决背包问题*需要背包容量*背包价值*背包剩余容量*解向量集合*/private double total_weight;private double total_value;private double rest_weight;//储存排序数组private Good[] arrayValue;private Good[] arrayWeight;private Good[] arrayC_P;private int goodsNum;private Good[] goods;private double real_weight;public Greedy() {}public Greedy(int goodsNum,double total_weight) {this.goodsNum=goodsNum;this.total_weight=total_weight;}public void init(String filename) throws IOException {/** 1.初始化程序* 2.从TXT⽂件中得到商品重量和其价值数组* 3.初始化序列数组arrayValue/Weight/C_P*/goods=new Good[goodsNum];BufferedReader data=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));String buff;String[] strs;//循环赋值for(int i=0;i<4;i++){buff=data.readLine();strs=buff.split(" ");//根据位次goods[i]=new Good();//对象数组不仅仅需要初始化数组，对于数组内的每⼀个对象也需要初始化goods[i].setName(strs[0]);goods[i].setValue(Double.parseDouble(strs[1]));goods[i].setWeight(Double.parseDouble(strs[2]));goods[i].figureC_P();}//关闭输⼊流//成员变量初始化arrayValue=new Good[goodsNum];arrayWeight=new Good[goodsNum];arrayC_P=new Good[goodsNum];//初始化数组/** 价值由⼤到⼩数组*/arrayValue=arrayCopy(goods, arrayValue);//按照价值对arrayValue数组进⾏重新排列，使⽤冒泡排序法for(int i=0;i<goodsNum-1;i++){//从⼤到⼩排列for(int j=i+1;j<goodsNum;j++){if(arrayValue[i].getValue()<arrayValue[j].getValue()){Good temp=arrayValue[i];arrayValue[i]=arrayValue[j];arrayValue[j]=temp;}}}/**质量由⼩到⼤数组*/arrayWeight=arrayCopy(goods, arrayWeight);//按照价值对arrayWeight数组进⾏重新排列，使⽤冒泡排序法for(int i=0;i<goodsNum-1;i++){//从⼩到⼤排列for(int j=i+1;j<goodsNum;j++){if(arrayWeight[i].getWeight()>arrayWeight[j].getWeight()){Good temp=arrayWeight[i];arrayWeight[i]=arrayWeight[j];arrayWeight[j]=temp;}}}/** 性价⽐由⼤到⼩排列*/arrayC_P=arrayCopy(goods, arrayC_P);//按照价值对arrayC_P数组进⾏重新排列，使⽤冒泡排序法for(int i=0;i<goodsNum-1;i++){//从⼤到⼩排列for(int j=i+1;j<goodsNum;j++){if(arrayC_P[i].getC_P()<arrayC_P[j].getC_P()){Good temp=arrayC_P[i];arrayC_P[i]=arrayC_P[j];arrayC_P[j]=temp;}}}}//⽤于数组拷贝public Good[] arrayCopy(Good[] goods,Good[] arr2){arr2=goods.clone();return arr2;}private void show(Good[] goodsarr) {for(Good good:goodsarr){System.out.println(good.getName()+"\t"+good.getValue()+"\t"+good.getWeight()+"\t"+good.getC_P()+"\t"+good.getNum()); }}/*三种策略：度量准则* 依次选取价值最⼤填充* 依次选取重量最轻填充* 依次选取⽐价最⼤填充** ⽅法设计：* 按照度量准则* 传递⼀个按照选择优先级排列的对象数组* 迭代计算剩余容量* 返回设计⽅案*/public void strategy(Good[] goodsArray){rest_weight=total_weight;for(Good good:goodsArray){int selectNum=(int)Math.floor(rest_weight/good.getWeight());rest_weight=rest_weight-selectNum*good.getWeight();good.setNum(selectNum);if(rest_weight<arrayWeight[0].getWeight()){continue;}}}public void calculate(Good[] goodsArray,String target){total_value=0;real_weight=0;//处理结果System.out.println("在以"+target+"为准则的情况下");for(Good good:goodsArray){System.out.println(good.getName()+"\t\t数量："+good.getNum());total_value+=good.getValue()*good.getNum();real_weight+=good.getWeight()*good.getNum();}System.out.println("总价值是:\t"+total_value+"\t总重量是:\t"+real_weight); }public void solve() {/** 业务逻辑* 将优先级数组*/strategy(arrayValue);calculate(arrayValue,"价值");strategy(arrayWeight);calculate(arrayWeight,"重量");strategy(arrayC_P);calculate(arrayC_P,"⽐值");}public static void main(String[] args) throws IOException {Greedy greedy=new Greedy(4,50);greedy.init("goods.txt");greedy.solve();}}Txt⽂本为：ad钙奶 12 5ab胶带 6 1电脑 4000 30⾳响 500 15说明：第⼀列：名称第⼆列：价格第三列：重量程序运⾏结果为：待改善。

实验五：贪心算法求解背包问题实验内容应用贪心算法求解离散背包问题，分析时间复杂度。

有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vi （1<=i<=n），设求这些物品中最有价值的一个子集。

如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。

算法思想•动态规划的思想：–对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，求解出较大问题的解，直到求解出最大问题的解。

–引进一个二维数组ch[MAX][MAX]，用ch[i][j]记录CH1与CH2的LCS的长度，b[i][j]记录ch[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。

我们是自底向上进行递推计算，那么在计算ch[i,j]之前，ch[i-1][j-1]，ch[i-1][j]与ch[i][j-1]均已计算出来。

此时我们根据CH1 [i] = CH2[j]还是CH1[i] !=CH2[j]，就可以计算出ch[i][j]。

算法length(string CH1,string CH2,int b[MAX][MAX])//用于构建动态数组//输入：两字符窜//输出：最长公共子序列for(i=1;i<=ch1Len;i++)//二重循环求解for(int j=1;j<=ch2Len;j++){if(CH1[i-1]==CH2[j-1])//相等字符{ch[i][j]=ch[i-1][j-1]+1;b[i][j]=0;}else if(ch[i-1][j]>=ch[i][j-1])//上比较大{ch[i][j]=ch[i-1][j];b[i][j]=1;}else//左比较大{ch[i][j]=ch[i][j-1];b[i][j]=-1;}}printCS(int b[MAX][MAX],string x,int i,int j) //回溯求出最长子序列输出//输入：标记数组//输出：最长子序列if(i == 0 || j == 0)//边界，返回return;if(b[i][j] == 0){printCS(b, x, i-1, j-1);//左上cout<<x[i-1]<<" ";}else if(b[i][j] == 1)printCS(b, x, i-1, j);//上elseprintCS(b, x, i, j-1);//左源程序//应用贪心算法求解离散背包问题#include<iostream>using namespace std;#define MAX 100//结构体struct Elem{double W;double V;double P;int number;};//顺序表struct SqList{Elem *elem;int length;int listsize;};//构造一个空的线性顺序表void InitList_Sq(SqList &L){L.elem=(Elem *)malloc(100*sizeof(Elem)); L.length=0;L.listsize=100;}//******************************** //构造背包,顺序表//******************************void input(SqList &L){cout<<"请输入物品的个数：";cin>>L.length;for(int i=0;i<L.length;i++){cout<<"请输入第"<<i+1<<"个物品的重量和价值：";cin>>L.elem[i].W>>L.elem[i].V;L.elem[i].P=L.elem[i].V/L.elem[i].W;cout<<"价值比为："<<L.elem[i].P<<endl;L.elem[i].number=i+1;}}//*********************************//插入排序由大到小//*******************************void inser(SqList &L){Elem inserter;int index;//inserter待插入合适位置的元素,index指示插入位置for(int pass=1;pass<L.length;pass++){//共比较size-1轮inserter=L.elem[pass];//第pass轮时,待插入的对象是a[pass] index=pass-1;while(index>=0&&inserter.P>L.elem[index].P){ //寻找插入位置L.elem[index+1]=L.elem[index];index--;//指针前移，再比较}L.elem[index+1]=inserter;//跳出while时，找到插入位置}//end of forcout<<"按照价值比由大到小排列的顺序为：";for(pass=0;pass<L.length;pass++)cout<<L.elem[pass].number<<" ";cout<<endl;}//*************************************************8 //背包程序//采用贪心算法//根据价值和重量的比来实现贪心算法//************************************************ void bag(SqList L){double w,sumV=0,sumW=0;int list[MAX],a=0;cout<<"请输入背包承重量W:";cin>>w;inser(L);for(int i=0;i<L.length;i++){while(sumW+L.elem[i].W<=w){sumW=sumW+L.elem[i].W;sumV=sumV+L.elem[i].V;list[a++]=L.elem[i].number;}}cout<<"最后包里的总重量为："<<sumW<<endl; cout<<"最后包里的总价值为："<<sumV<<endl; cout<<"放到背包中的物品的序号列表为："; for(i=0;i<a;i++){cout<<list[i]<<" ";}}int main(){cout<<"贪心算法求解背包问题"<<endl;SqList L;InitList_Sq(L);input(L);bag(L);return 0;}实验结论1、运行截图查找最长公共子序列长度时的动态规划两个for循环，时间复杂度为Ｏ（ｎ＊ｎ）。

《算法设计与分析》实验报告2015-2016年第2学期实验班级：学生姓名：学号：指导老师：信息工程学院实验项目名称：贪心算法背包问题实验日期：2016年4月12日一、实验类型：□√验证性□设计性二、实验目的1、掌握背包问题的算法2、初步掌握贪心算法三、实验内容及要求问题描述：与0-1背包问题相似，给定n种物品和一个背包。

物品i的重量是wi，其价值为vi，背包的容量为c。

与0-1背包问题不同的是，在选择物品i装入背包时，背包问题的解决可以选择物品i的一部分，而不一定要全部装入背包，1< i < n。

四、实验步骤#include "iostream.h"#include "stdio.h"#include <cstdlib>struct stone{ int name;int weight;//物品的剩余重量int weight_t;//物品的重量float benefit;//物品的价值//float b;};void sort(stone *data,int num){if(num<1)return;int low=0,high=num;stone key_s=data[low];float key=(float)key_s.benefit/key_s.weight;int empty=low;while(low<high){ if(low==empty){ while((data[high].benefit/data[high].weight<key) &&(high>low)){ high--;}if(data[high].benefit/data[high].weight>=key){ data[low]=data[high];empty=high;}}else if(high==empty) {while((data[low].benefit/data[low].weight>=key)&&(low<h igh)){ low++; }if(data[low].benefit/data[low].weight<key){ data[high]=data[low];empty=low; }}}data[empty]=key_s;if(empty>1)sort(data,empty-1);if(num-empty-1>0)sort(data+empty+1,num-empty-1);}void inputstone(stone *bag,int num){ for(int i=0;i<num;i++){ bag[i].name=i+1;printf("请输入第%d号物品的重量:",i+1); scanf("%d",&bag[i].weight);if (bag[i].weight<=0){printf("物品的重量必须大于0!\n");} printf("请输入第%d号物品的价值:",i+1); scanf("%f",&bag[i].benefit);if (bag[i].benefit<=0){printf("物品的价值必须大于0!\n");}bag[i].weight_t=bag[i].weight;}}int main(int argc, char* argv[]){ int i;int num=0;int weight=0;float benefit=0;stone *bag;do{ printf("请输入背包可容纳的重量:"); scanf("%d",&weight);if (weight<=0)printf("背包可容纳的重量必须大于0!\n"); }while(weight<=0);do{ printf("请输入物品的数量:");scanf("%d",&num);if (num<=0)printf("物品数量必须大于0!\n");}while(num<=0);bag=new stone[num];inputstone(bag,num);sort(bag,num-1);for(i=0;i<num&&weight>0;i++){ stone *temp=bag+i;if(weight>=temp->weight){ weight-=temp->weight;temp->weight=0;benefit+=temp->benefit;continue;}else{ temp->weight-=weight;weight=0;benefit+=(temp->benefit*(1-(float)temp->weight/temp->we ight_t));break;} }printf("物品种类放入的比例每单位效益\n");for(i=0;i<num;i++){ stone *temp=bag+i;printf("%d类物品",temp->name);printf("\t\t%.2f\t\t",(temp->weight_t-temp->weight)/(fl oat)temp->weight_t);printf(" %.4f\n",temp->benefit/(float)temp->weight_t) ;}printf("总效益:%.2f",benefit);delete bag;getchar();system("PAUSE");return EXIT_SUCCESS;return 0;}五、实验结果1、实验图形2、结果分析如上面第一个图所示当输入背包可容纳的重要为21，输入物品的数量为3，输入第1号物品的重量为8，输入第1号物品的价值为12，输入第2号物品的重量为9，输入第2号物品的价值为16，输入第3号物品的重量为4，输入第3号物品的价值为15，则可以得出总效益为43.00。

贪心法求解最佳装载背包问题描述：对于容量为c的背包进行装载，从n个物品中选择装入背包的物品，每个物品i的重量和价值分别为wi和pi。

在背包中物品的总重量不超过背包容量的前提下，求装入物品价值最高的装载法。

输入：5 20 //物品的数量和背包的容量6 3 //第一个物品的重量和价值2 5 //…3 810 67 4输出：1110.714286算法如下：#include <stdio.h>#include <stdlib.h>struct goodinfo//物品结构体{float p;//价值float w;//重量float x;//数量int flag;//标志变量};void Insertionsort(struct goodinfo goods[],int n)//将物品根据价值排序{int i,j;for(j=2;j<=n;j++){goods[0]=goods[j];//保存比较的对象i=j-1;while(goods[0].p>goods[i].p)//找到位置后退出{goods[i+1]=goods[i];//错位i--;}goods[i+1]=goods[0];//找到位置后将比较的对象覆盖}}void bag(struct goodinfo goods[],float M,int n){float cu;//剩余空间int i,j;for(i=1;i<=n;i++)goods[i].x=0;//初始化cu=M;//初始化for(i=1;i<=n;i++){if(goods[i].w>cu)break;goods[i].x=1;cu=cu-goods[i].w;}if(i<=n)goods[i].x=cu/goods[i].w;//将物品分割for(j=2;j<=n;j++)//按照物品的编号排序，便于输出goods[0]=goods[j];i=j-1;while(goods[0].flag<goods[i].flag){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}printf("最优解为：\n");for(i=1;i<=n;i++){printf("第%d件物品要放：%f\n",i,goods[i].x);}}int main(){int j=1,n,i;float M;while(j)system("cls");printf("输入物品的总数：");scanf("%d",&n);struct goodinfo goods[n+1];//动态定义结构体数组的大小printf("背包最大容量：");scanf("%f",&M);for(i=1;i<=n;i++){goods[i].flag=i;printf("weight input:");scanf("%f",&goods[i].w);printf("price input:");scanf("%f",&goods[i].p);goods[i].p/=goods[i].w;}Insertionsort(goods,n);bag(goods,M,n);printf("press <1> to run again\npress <0> to exit\n请输入操作码：");scanf("%d",&j);}return 0; }。

python实现贪婪算法解决01背包问题⼀、背包问题01背包是在M件物品取出若⼲件放在空间为W的背包⾥，每件物品的体积为W1，W2⾄Wn，与之相对应的价值为P1,P2⾄Pn。

01背包是中最简单的问题。

01背包的约束条件是给定⼏种物品，每种物品有且只有⼀个，并且有权值和体积两个属性。

在01背包问题中，因为每种物品只有⼀个，对于每个物品只需要考虑选与不选两种情况。

如果不选择将其放⼊背包中，则不需要处理。

如果选择将其放⼊背包中，由于不清楚之前放⼊的物品占据了多⼤的空间，需要枚举将这个物品放⼊背包后可能占据背包空间的所有情况。

⼆、求解思路 当遇到这样的问题，我们可以换⼀种⾓度去思考，假设在⼀个100m3的房⼦⾥⾯，现在要将房⼦装满，同时要保证放⼊的物品个数最多以及装⼊的东西最重，现在⾝边有铁球和棉花，请问⼤家是放铁球进去好呢还是放棉花进去好呢？显⽽易见，放⼊铁球进去是最优选择。

但是原因是什么呢？很简单，就是因为铁球的密度较⼤，相同体积的铁球和棉花相⽐，铁球更重。

不过前提是放⼊第⼀个铁球时，铁球的体积V1⼩于等于100m3 ；放⼊第⼆个铁球时，铁球的体积V2 ⼩于等于(100-V1)m3;……；放⼊第n个铁球时，铁球的体积⼩于等于（100-∑n1Vn-1）m3 ，要是第n个铁球的体积⼤于（100- ∑n1Vn-1）m3 ，还真是不如放点单位体积更轻的棉花进去，说的极端点就是所有铁球的体积都⼤于100m3 ，还真不如随便放⼊点棉花进去合算。

所以总是放铁球进去，不考虑是否放⼊棉花，容易产⽣闲置空间，最终会得不到最优选择，可能只是最优选择的近似选择。

现在再次回到背包问题上，要使得背包中可以获得最⼤总价值的物品，参照铁球的例⼦我们可以知道选择单位重量下价值最⾼的物品放⼊为最优选择。

但是由于物品不可分割，⽆法保证能将背包刚好装满，最后闲置的容量⽆法将单位重量价值更⾼的物品放⼊，此时要是可以将单位重量价值相对低的物品放⼊，反⽽会让背包的总价值和单位重量的价值更⾼。

Python基于贪⼼算法解决背包问题⽰例本⽂实例讲述了Python基于贪⼼算法解决背包问题。

分享给⼤家供⼤家参考，具体如下：贪⼼算法（⼜称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪⼼算法不是对所有问题都能得到整体最优解，关键是贪⼼策略的选择，选择的贪⼼策略必须具备⽆后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

完全背包问题：给定n个物品和⼀个容量为C的背包，物品i的重量是Wi,其价值为Vi,背包问题是如何选择⼊背包的物品，使得装⼊背包的物品的总价值最⼤，与0-1背包的区别是，在完全背包问题中，可以将物品的⼀部分装⼊背包，但不能重复装⼊。

设计算法的思路很简单，计算物品的单位价值，然后尽可能多的将单位重量价值⾼的物品放⼊背包中。

python实现代码如下：# coding=gbk# 完全背包问题，贪⼼算法import time__author__ = 'ice'class goods:def __init__(self, goods_id, weight=0, value=0):self.id = goods_idself.weight = weightself.value = value# 不适⽤于0-1背包def knapsack(capacity=0, goods_set=[]):# 按单位价值量排序goods_set.sort(key=lambda obj: obj.value / obj.weight, reverse=True)result = []for a_goods in goods_set:if capacity < a_goods.weight:breakresult.append(a_goods)capacity -= a_goods.weightif len(result) < len(goods_set) and capacity != 0:result.append(goods(a_goods.id, capacity, a_goods.value * capacity / a_goods.weight))return resultsome_goods = [goods(0, 2, 4), goods(1, 8, 6), goods(2, 5, 3), goods(3, 2, 8), goods(4, 1, 2)]start_time = time.clock()res = knapsack(6, some_goods)end_time = time.clock()print('花费时间：' + str(end_time - start_time))for obj in res:print('物品编号:' + str(obj.id) + ' ,放⼊重量:' + str(obj.weight) + ',放⼊的价值:' + str(obj.value), end=',')print('单位价值量为:' + str(obj.value / obj.weight))# 花费时间：2.2807240614677942e-05# 物品编号:3 ,放⼊重量:2,放⼊的价值:8,单位价值量为:4.0# 物品编号:0 ,放⼊重量:2,放⼊的价值:4,单位价值量为:2.0# 物品编号:4 ,放⼊重量:1,放⼊的价值:2,单位价值量为:2.0# 物品编号:1 ,放⼊重量:1,放⼊的价值:0.75,单位价值量为:0.75更多关于Python相关内容感兴趣的读者可查看本站专题：《》、《》、《》、《》、《》及《》希望本⽂所述对⼤家Python程序设计有所帮助。

贪心算法--0-1背包问题1、问题的描述有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,4,2,1,3，它们的价值分别是3,5,6,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？贪心算法的思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。

也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。

2、代码及注释#include <stdio.h>#define M 5//定义一个node结构体，用来存放物体的重量和价值struct node{float value;//价值float weight;//重量int flag; //用来判别这个物体是否装进背包}Node[M],temp;float Value,curvalue=0;//总价值和当前价值float Weight,curweight=0;//背包的最大承受重量和现有重量//按性价比排序void sort(){int i,j;//遍历所有物品for(i=0;i<M-1;i++){//与之后的物品进行比较for(j=i+1;j<M;j++){//判断性价比较最高性价比if((Node[i].value/(float)Node[i].weight)<Node[j].value/(float)Node[j].weight) {//进行交换temp=Node[i];Node[i]=Node[j];Node[j]=temp;}}}}//装载主要方法void load(){int i;//遍历所有物品for(i=0;i<M;i++){//判断加入物品否是否大于背包所能承载的最大重量 if((Node[i].weight+curweight)<=Weight){curvalue+=Node[i].value;curweight+=Node[i].weight;Node[i].flag=1;//进行标记}else{//进行标记Node[i].flag=0;}}}//进行结果的输出void putout(){int i;printf("选中物品的重量分别为：");for(i=0;i<M;i++){if(Node[i].flag){printf("%.2f ",Node[i].weight);}}printf("\n总价值为:%.2f",curvalue);}int main(){int i;printf("请输入物品的重量和价值：\n");for(i=0;i<M;i++){printf("请输入第%d个物品的重量和价值",i+1); scanf("%f%f",&Node[i].weight,&Node[i].value);}printf("\n请输入背包容积：");scanf("%f",&Weight);sort();load();putout();return 0;}3、运行结果(1)在某种情况下可以通过局部最优选择达到整体最优。

贪心算法求解背包问题：#include<stdio.h>#define maxnumber 20typedef 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;for(i=1;i<=n;i++)//初始化x[n];{x[i]=0.0;}i=0;while(wp[i].w < M){x[wp[i].i]=1;M=M-wp[i].w;i++;}x[wp[i].i]=M/wp[i].w;//输出解向量printf("解向量是：\n");for(i=1;i<=n;i++){printf("x[%d]=%f",i,x[i]);}printf("\n");//计算最大价值for(i=0;i<n;i++){maxprice=maxprice+wp[i].v*x[wp[i].i];}return maxprice;}void main(){Object wp[maxnumber];int i,j,n;float C;//背包的重量int flag;float maxprice,temp;printf("请输入物品的种数:");scanf("%d",&n);printf("请输入背包的重量:");scanf("%f",&C);printf("\n请输入物品的序号、重量和价值：");for(i=0;i<n;i++){scanf("%d",&wp[i].i);scanf("%f",&wp[i].w);scanf("%f",&wp[i].v);}printf("\n输入的物品是：\n");//输出物品for(i=0;i<n;i++){printf(" %d",wp[i].i);printf(" %f",wp[i].w);printf(" %f",wp[i].v);printf("\n");}//用冒泡排序对物品按照单位价值进行降序排序for(i=1;i<n;i++){flag=0;for(j=n-1;j>=i;j--){if(wp[j-1].v/wp[j-1].w < wp[j].v/wp[j].w){temp=wp[j-1].i;wp[j-1].i=wp[j].i;wp[j].i=temp;temp=wp[j-1].w;wp[j-1].w=wp[j].w;wp[j].w=temp;temp=wp[j-1].v;wp[j-1].v=wp[j].v;wp[j].v=temp;flag=1;}if(flag==0)break;}}printf("\n排序后的物品是：\n");//输出物品for(i=0;i<n;i++){printf(" %d",wp[i].i);printf(" %f",wp[i].w);printf(" %f",wp[i].v);printf("\n");}maxprice=find(wp,n,C);printf("\n物品的重价值为：%f",maxprice);}。

基于朴素贪心算法的背包问题解决方案背包问题是一类经典的组合优化问题，它的一般形式描述为：有一个固定大小的背包，和一些物品，每个物品都有自己的价值和大小，需要选出一些物品装入背包中，使得装进去的物品价值最大化，同时又不能超出背包容量的限制。

这个问题在实际生活中有很多应用，比如在货物的装载和运输、在零售商的库存管理、在网页推荐系统等等。

解决背包问题的方法有很多，其中比较经典的是基于动态规划的解法，但是这种解法需要使用大量的存储空间，如果物品数量很大的话，计算复杂度也会很高。

因此本文将介绍一种基于朴素贪心算法的背包问题解决方案。

一、背包问题的数学模型在介绍具体的解决方案之前，我们需要先来看一下背包问题的数学模型。

假设我们有n个物品，第i个物品的重量为wi，价值为vi，背包的容量为W。

那么背包问题可以用下面的数学模型来描述：$$\begin{aligned}&\max\sum_{i=1}^{n}v_ix_i\\&s.t.\sum_{i=1}^ {n}w_ix_i\leq W\\&x_i\in \{0,1\}\end{aligned}$$其中，$x_i$表示第$i$个物品是否被选中，$v_i$和$w_i$分别表示第$i$个物品的价值和重量。

第一个约束条件表示所有选中的物品的总重量不能超过背包的容量$W$，第二个约束条件表示每个物品最多只能选一次。

二、基于朴素贪心算法的解法朴素贪心算法的思路很简单：每次选择可行的物品中价值最大的那一个，直到不能再选为止。

对于背包问题来说，我们可以按照物品的单位价值（即价值与重量比值）从大到小排序，然后依次选择可行的物品加入背包中。

具体步骤如下：1. 计算每个物品的单位价值，按照单位价值从大到小排序。

2. 依次加入可行的物品，直到不能再加入为止。

3. 最后得到的物品组合就是背包问题的最优解。

该算法的时间复杂度为$O(nlogn)$，其中$n$为物品的数量。

算法设计与分析实验报告实验名称 贪心算法实现背包问题 评分 实验日期 年 月 日 指导教师 姓名 专业班级 学号一.实验要求1. 优化问题有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组 成，而把满足约束条件的子集称为该问题的可行解。

可行解一般来说是不唯一的。

那些使目标函数取极值(极大或极小)的可行解，称为最优解。

2.贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方法。

在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。

决策一旦作出，就不可再更改。

作出贪心决策的依据称为贪心准则（greedy criterion）。

3.一般方法1）根据题意，选取一种量度标准。

2）按这种量度标准对这n个输入排序3）依次选择输入量加入部分解中。

如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。

procedure GREEDY(A，n) /*贪心法一般控制流程*///A(1：n)包含n个输入//solutions←φ //将解向量solution初始化为空／for i←1 to n dox←SELECT(A)if FEASIBLE(solution，x)then solutions←UNION(solution，x)endifrepeatreturn(solution)end GREEDY4. 实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。

二.实验内容1. 编程实现背包问题贪心算法。

通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。

2.输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。

3.将统计数与复杂性函数所计算比较次数比较，用表格列出比较结果，给出文字分析。

三.程序算法1. 背包问题的贪心算法procedure KNAPSACK(P，W，M，X，n)//P(1：n)和W(1；n)分别含有按P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值和重量。

2贪心算法解决部分背包问题一、实验目的学习掌贪心算法法思想。

二、实验内容用贪心法解决部分背包问题。

给定n种物品和一个背包。

物品i的重量是Wi，其价值为pi，背包的容量为M，将物品i的一部分xi放入背包会得到pi xi的效益。

应如何选择装入背包的物品，使得装入背包中物品的总价值最大?给出具体的装包方案。

在选择装入背包的物品时，对每种物品i，可以整件装入背包、不装入背包或部分装入背包。

但不能将物品i装入背包多次。

四、需求分析对于给定n种物品和一背包。

在容量最大值固定的情况下，要求装入的物品价值最大化。

五、基本思想：贪婪法是解决最优化问题时的一种简单但适用范围有限的策略。

总是对当前的问题作最好的选择，也就是局部寻优。

最后得到整体最优。

总是选择单位价值最高的物品。

六、详细设计#include<iostream>using namespace std;struct _Object//物品结构体{int Value;//物品价值int Weight;//物品重量int AveValue;//物品单位价值float Num;//物品可以放入的数量void knaspsack(int n,float M,_Object object[]){ //n为物品个数，M为背包容量int i;float C=M;for(i=0;i<n;i++){object[i].Num=0;//初始化放入背包的物品为0if(object[i].Weight>C)break;//当物品重量大于背包容量时else//小于时{object[i].Num=1;//物品i放入一件C-=object[i].Weight;//背包容量减小}}if(i<=n)//当不能放入整个物品时，选取物品一部分放入object[i].Num=C/object[i].Weight;for(i=0;i<n;i++){if(object[i].Num>0)cout<<"重量为: "<<object[i].Weight<<" 价值为: "<<object[i].Value<<" 的物品放入"<<object[i].Num<<" 件"<<endl;}}void SortObject(_Object object[],int n)//将各个物品按单位价值进行排序{int j;_Object temp;int i;for(i=0;i<n;i++)object[i].AveValue=object[i].Value/object[i].Weight;//各个物品的单位价值for(i=0;i<n-1;i++)//根据物品的单位价值对物品进行从大到小的冒泡排序{for(j=0;j<n-i-1;j++){if(object[j].AveValue<object[j+1].AveValue){temp=object[j];object[j]=object[j+1];object[j+1]=temp;}}}}int main(){_Object object[4];//4个物品int M=9;//背包容量为15object[0].Weight=2;object[0].Value=3;object[1].Weight=3;object[1].Value=4;object[2].Weight=4;object[2].Value=5;object[3].Weight=5;object[3].Value=7;SortObject(object,4);knaspsack(4,M,object);}七、结果分析：对于0-1背包问题，贪心算法之所以不能得到最优解是因为在这种情况下，它无法保证最后能将背包装满，部分闲置的背包空间，使每公斤背包的价值降低了。