下载文档原格式
贪⼼算法-01背包问题1、问题描述：给定n种物品和⼀背包。
物品i的重量是wi，其价值为vi，背包的容量为C。
问:应如何选择装⼊背包的物品，使得装⼊背包中物品的总价值最⼤?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找⼀n元向量(x1,x2,…,xn,), xi∈{0,1}, ∋ ∑ wi xi≤c,且∑ vi xi达最⼤.即⼀个特殊的整数规划问题。
2、最优性原理：设(y1,y2,…,yn)是 (3.4.1)的⼀个最优解.则(y2,…,yn)是下⾯相应⼦问题的⼀个最优解:证明:使⽤反证法。
若不然,设(z2,z3,…,zn)是上述⼦问题的⼀个最优解,⽽(y2,y3,…,yn)不是它的最优解。
显然有∑vizi > ∑viyi (i=2,…,n)且 w1y1+ ∑wizi<= c因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的⼀个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,⽭盾。
3、递推关系：设所给0-1背包问题的⼦问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。
由0-1背包问题的最优⼦结构性质，可以建⽴计算m(i，j)的递归式:注:(3.4.3)式此时背包容量为j，可选择物品为i。
此时在对xi作出决策之后,问题处于两种状态之⼀:(1)背包剩余容量是j,没产⽣任何效益；(2)剩余容量j-wi,效益值增长了vi ；使⽤递归C++代码如下：#include<iostream>using namespace std;const int N=3;const int W=50;int weights[N+1]={0,10,20,30};int values[N+1]={0,60,100,120};int V[N+1][W+1]={0};int knapsack(int i,int j){int value;if(V[i][j]<0){if(j<weights[i]){value=knapsack(i-1,j);}else{value=max(knapsack(i-1,j),values[i]+knapsack(i-1,j-weights[i]));}V[i][j]=value;}return V[i][j];}int main(){int i,j;for(i=1;i<=N;i++)for(j=1;j<=W;j++)V[i][j]=-1;cout<<knapsack(3,50)<<endl;cout<<endl;}不使⽤递归的C++代码：简单⼀点的修改//3d10-1 动态规划背包问题#include <iostream>using namespace std;const int N = 4;void Knapsack(int v[],int w[],int c,int n,int m[][10]);void Traceback(int m[][10],int w[],int c,int n,int x[]);int main(){int c=8;int v[]={0,2,1,4,3},w[]={0,1,4,2,3};//下标从1开始int x[N+1];int m[10][10];cout<<"待装物品重量分别为："<<endl;for(int i=1; i<=N; i++){cout<<w[i]<<" ";}cout<<endl;cout<<"待装物品价值分别为："<<endl;for(int i=1; i<=N; i++){cout<<v[i]<<" ";}cout<<endl;Knapsack(v,w,c,N,m);cout<<"背包能装的最⼤价值为："<<m[1][c]<<endl;Traceback(m,w,c,N,x);cout<<"背包装下的物品编号为："<<endl;for(int i=1; i<=N; i++){if(x[i]==1){cout<<i<<" ";}}cout<<endl;return 0;}void Knapsack(int v[],int w[],int c,int n,int m[][10]){int jMax = min(w[n]-1,c);//背包剩余容量上限范围[0~w[n]-1] for(int j=0; j<=jMax;j++){m[n][j]=0;}for(int j=w[n]; j<=c; j++)//限制范围[w[n]~c]{m[n][j] = v[n];}for(int i=n-1; i>1; i--){jMax = min(w[i]-1,c);for(int j=0; j<=jMax; j++)//背包不同剩余容量j<=jMax<c{m[i][j] = m[i+1][j];//没产⽣任何效益}for(int j=w[i]; j<=c; j++) //背包不同剩余容量j-wi >c{m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//效益值增长vi }}m[1][c] = m[2][c];if(c>=w[1]){m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);}}//x[]数组存储对应物品0-1向量,0不装⼊背包，1表⽰装⼊背包void Traceback(int m[][10],int w[],int c,int n,int x[]){for(int i=1; i<n; i++){if(m[i][c] == m[i+1][c]){x[i]=0;}else{x[i]=1;c-=w[i];}}x[n]=(m[n][c])?1:0;}运⾏结果：算法执⾏过程对m[][]填表及Traceback回溯过程如图所⽰：从m(i，j)的递归式容易看出，算法Knapsack需要O(nc)计算时间; Traceback需O(n)计算时间；算法总体需要O(nc)计算时间。
实验项目名称：贪心算法求连续背包问题一、实验目的：明确连续背包问题的概念；利用贪心算法解决连连续续背包问题；并通过本例熟悉贪心算法在程序设计中的应用方法。
二、实验原理： 贪心算法原理：在贪婪算法（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");}。
算法分析与设计实验报告第四次实验
}
}
输入较小的结果：
测试结
果
输入较大的结果：
附录：
完整代码（贪心法）
;
cout<<endl;
cout<<"待装物品的价值为："<<endl;
for (i=0;i<n;i++)
cin>>item[i].v;
cout<<endl;
erval=item[i].v/item[i].w;
clock_t start,end,over; ;
实验心
得
首先这个实验，需要注意的点是背包问题与0-1背包不同，物品可以部分的放入背包中，所以思路也不一样，首先就是将物品按照单位质量价值排序，只这一点就有一点难度。
难度在于要是排序后物品的编号就会发生改变，输出的就不是之前的编号的物品，导致错误，后来发现如果为每一个物品保存一个副本，然后将它们的编号进行对比，就可以进行正确的输出了。
其中这个实验
让我学到了两点：一是结构体的使用，之前一直没有怎么用过，现在才发现自己其实不会用；二十对于库函数sort 函数的使用。
感觉每一次实验都有学到东西，很开心。
实验得
分 助教签名
sort(item,item+n,comparison); >c)
break;
tem[i]=1;
c-=item[i].w;
}
if(i<n) ;
for(i=0;i<n;i++) ==tmp[j])
x[j]=tem[i];
}
}
}。
0—1背包问题一、实验目的学习掌贪心算法法思想。
二、实验内容用分支限定法求解0—1背包问题，并输出问题的最优解。
0—1背包问题描述如下：给定n种物品和一背包。
物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。
三、实验条件Jdk1.5以上四、需求分析对于给定n种物品和一背包。
在容量最大值固定的情况下，要求装入的物品价值最大化。
五、基本思想：总是对当前的问题作最好的选择，也就是局部寻优。
最后得到整体最优。
总是选择单位价值最高的物品六、详细设计package sunfa;/**** @author Administrator*/import java.util.*;public class Greedy_Algorithm {static Element dd[];static int CurrentV ;static int CurrentC;static StringBuffer stb= new StringBuffer();public static int knapasck(int c, int[] w, int[] v, int[] x) {int n = v.length;Element d [] = new Element[n];for(int i = 0 ;i< n; i++){d[i]=new Element(w[i],v[i],i+1);}//按单位重量价值升序排序Arrays.sort(d);dd =d;/*for(int i = 0; i<d.length ;i++){System.out.println("重量" +d[i].ww+ "单位价值"+d[i].wv);}*/int i = 0;int MaxV2 = 0;for(i=0;i<n;i++)x[i] = 0;for(i=0;i<n;i++){if(d[i].ww>c)break;else{x[i] = d[i].tag; //x【】中存的是原元素的序号MaxV2 = MaxV2+d[i].value;c = c -d[i].ww;CurrentC =c ;stb.append("选择第" + d[i].tag + "个当前价值:"+MaxV2+ "剩余容量:"+c+"\n");}}return MaxV2;}}class Element implements Comparable{int ww; //物品重量int value; //物品价值double wv;//物品单位重量的价值int tag;//物品的标志是第一个物品public Element(int w ,int vv ,int tag){this.tag = tag;this.ww = w;this.value = vv;wv = (double)vv/w;}//对象比较的方法public int compareTo(Object x){Element temp = (Element)x;double rate = (double)ww/value;double temprate = (double)temp.ww/temp.value;if(rate<temprate)return -1;if(rate==temprate)return 0;elsereturn 1;}}运行结果(用列一)用列二上述结果显示:贪心算法不是总是最优的.动态规划与贪心算法比较;动态规划法又和贪婪算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。
贪心法的关键是度量标准，这个程序的度量标准有三个占用空间最小物品效益最大物品效益/占用空间最大程序实现如下：至于文件的操作不加论述。
#include <stdio.h>#include <stdlib.h>typedef struct{char name[10];int weight;int price;}Project;Project *Input(Project *wp,int TotalNum,int TotalWeight) {int i,j,Way,GoBack,RealWeight,RealPrice,TotalPrice;Project temp;do{printf("请选择:\n");printf(" 1.空间最优\n");printf(" 2.价格最优\n");printf(" 3.价格空间比最优\n");scanf("%d",&Way);switch(Way){case 1:for(i=0;i<TotalNum;i++)for(j=0;j<TotalNum-i-1;j++){if(wp[j].weight>wp[j+1].weight){temp=wp[j];wp[j]=wp[j+1];wp[j+1]=temp;}}break;case 2:for(i=0;i<TotalNum;i++)for(j=0;j<TotalNum-i-1;j++){if(wp[j].price<wp[j+1].price){temp=wp[j];wp[j]=wp[j+1];wp[j+1]=temp;}}break;case 3:for(i=0;i<TotalNum;i++)for(j=0;j<TotalNum-i-1;j++){if((float)wp[j].price/(float)wp[j].weight<(float)wp[j+1].price/(float)wp[j+1].weight){temp=wp[j];wp[j]=wp[j+1];wp[j+1]=temp;}}break;default:{printf("输入错误!\n");exit(1);}}i=0;RealWeight=wp[0].weight;TotalPrice=wp[0].price;printf("被装入背包的物品是:\n(物品名价格重量)\n");while(RealWeight<TotalWeight&&i<TotalNum){printf("%s %d %d\n",wp[i].name,wp[i].price,wp[i].weight);i++;RealWeight+=wp[i].weight;TotalPrice+=wp[i].price;}RealWeight-=wp[i].weight;TotalPrice-=wp[i].price;printf("求解结束!背包所装物品总重量:%d,总价值:%d\n",RealWeight,TotalPrice);printf("退出本次测试请按0!\n");scanf("%d",&GoBack);}while(GoBack!=0);return wp;}void main(){int InputWay,TotalNum,i,TotalWeight,RealWeight,Goon,TotalPrice;Project *Array;FILE *fp;do{printf("请选择数据录入方式!\n");printf(" 1.文件读入\n");printf(" 2.键盘输入\n");scanf("%d",&InputWay);switch(InputWay){case 1:printf("请输入背包最大容量:");scanf("%d",&TotalWeight);fp=fopen("data.txt","r");fscanf(fp,"%d\n",&TotalNum);if((Array=(Project*)malloc(TotalNum*sizeof(Project)))==NULL){printf("内存已满,申请空间失败!\n");exit(1);}else{for(i=0;i<TotalNum;i++){fscanf(fp,"%s %d %d\n",&Array[i].name,&Array[i].price,&Array[i].weight);}}fclose(fp);Array=Input(Array,TotalNum,TotalWeight);break;case 2:printf("请输入物品数量及背包容量\n");scanf("%d%d",&TotalNum,&TotalWeight);if((Array=(Project*)malloc(TotalNum*sizeof(Project)))==NULL){printf("内存已满,申请空间失败!\n");exit(1);}else{printf("请输入:物品名价格重量\n");for(i=0;i<TotalNum;i++)scanf("%s%d%d",&Array[i].name,&Array[i].price,&Array[i].weight);}Array=Input(Array,TotalNum,TotalWeight);break;default:{printf("输入错误!\n");exit(1);}}printf("继续其他数据测试请按1\n");scanf("%d",&Goon);}while(Goon==1);delete Array;}。
算法分析实验报告贪心法解决背包问题学生姓名：专业：班级：学号:指导教师：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");}结果：。
实验四“0-1”背包问题一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划算法的理解。
二、实验内容:掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解方法，并分析其优缺点。
三、实验题1.“0-1”背包问题的贪心算法2.“0-1”背包问题的动态规划算法说明：背包实例采用教材P132习题六的6-1中的描述。
要求每种的算法都给出最大收益和最优解。
设有背包问题实例n=7，M=15,，(w0,w1,。
w6)=（2,3,5,7,1,4,1），物品装入背包的收益为：（p0，p1，。
，p6）=（10,5,15,7,6,18,3）。
求这一实例的最优解和最大收益。
四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。
五、实验程序// 贪心法求解#include<iostream>#include"iomanip"using namespace std;//按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组，运用冒泡排序void AvgBenefitsSort(float *arry_avgp,float *arry_p,float *arry_w ); //获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量float GetBestBenifit(float*arry_p,float*arry_w,float*arry_x,float u);int main(){float w[7]={2,3,5,7,1,4,1}; //物品重量数组float p[7]={10,5,15,7,6,18,3}; //物品收益数组float avgp[7]={0}; //单位毒品的收益数组float x[7]={0}; //最后装载物品的最优解数组const float M=15; //背包所能的载重float ben=0; //最后的收益AvgBenefitsSort(avgp,p,w);ben=GetBestBenifit(p,w,x,M);cout<<endl<<ben<<endl; //输出最后的收益system("pause");return 0;}//按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组，运用冒泡排序void AvgBenefitsSort(float *arry_avgp,float *arry_p,float *arry_w ) {//求出物品的单位收益for(int i=0;i<7;i++){arry_avgp[i]=arry_p[i]/arry_w[i];}cout<<endl;//把求出的单位收益排序，冒泡排序法int exchange=7;int bound=0;float temp=0;while(exchange){bound=exchange;exchange=0;for(int i=0;i<bound;i++){if(arry_avgp[i]<arry_avgp[i+1]){//交换单位收益数组temp=arry_avgp[i];arry_avgp[i]=arry_avgp[i+1];arry_avgp[i+1]=temp;//交换收益数组temp=arry_p[i];arry_p[i]=arry_p[i+1];arry_p[i+1]=temp;//交换重量数组temp=arry_w[i];arry_w[i]=arry_w[i+1];arry_w[i+1]=temp;exchange=i;}}}}//获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量float GetBestBenifit(float*arry_p,float*arry_w,float*arry_x,float u) {int i=0; //循环变量ifloat benifit=0; //最后收益while(i<7){if(u-arry_w[i]>0){arry_x[i]=arry_w[i]; //把当前物品重量缴入最优解数组benifit+=arry_p[i]; //收益增加当前物品收益u-=arry_w[i]; //背包还能载重量减去当前物品重量cout<<arry_x[i]<<" "; //输出最优解}i++;}return benifit; //返回最后收益}//动态规划法求解#include<stdio.h>#include<math.h>#define n 6void DKNAP(int p[],int w[],int M,const int m); void main(){int p[n+1],w[n+1];int M,i,j;int m=1;for(i=1;i<=n;i++){m=m*2;printf("\nin put the weight and the p:");scanf("%d %d",&w[i],&p[i]);}printf("%d",m);printf("\n in put the max weight M:");scanf("%d",&M);DKNAP(p,w,M,m);}void DKNAP(int p[],int w[],int M,const int m) {int p2[m],w2[m],pp,ww,px;int F[n+1],pk,q,k,l,h,u,i,j,next,max,s[n+1];F[0]=1;p2[1]=w2[1]=0;l=h=1;F[1]=next=2;for(i=1;i<n;i++){k=l;max=0;u=l;for(q=l;q<=h;q++)if((w2[q]+w[i]<=M)&&max<=w2[q]+w[i]){u=q;max=w2[q]+w[i];}for(j=l;j<=u;j++){pp=p2[j]+p[i];ww=w2[j]+w[i];while(k<=h&&w2[k]<ww){p2[next]=p2[k];w2[next]=w2[k];next++;k++;}if(k<=h&&w2[k]==ww){if(pp<=p2[k])pp=p2[k];k++;}else if(pp>p2[next-1]){p2[next]=pp;w2[next]=ww;next++;}while(k<=h&&p2[k]<=p2[next-1])k++;}while(k<=h){p2[next]=p2[k];w2[next]=w2[k];next=next+1;k++;}l=h+1;h=next-1;F[i+1]=next;}for(i=1;i<next;i++)printf("%2d%2d ",p2[i],w2[i]);for(i=n;i>0;i--){next=F[i];next--;pp=pk=p2[next];ww=w2[next];while(ww+w[i]>M&&next>F[i-1]){next=next-1;pp=p2[next];ww=w2[next];}if(ww+w[i]<=M&&next>F[i-1])px=pp+p[i];if(px>pk&&ww+w[i]<=M){s[i]=1;M=M-w[i];printf("M=%d ",M);}else s[i]=0;}for(i=1;i<=n;i++)printf("%2d ",s[i]);}六、实验结果1、贪心法截图：七、实验分析。
使⽤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说明：第⼀列：名称第⼆列：价格第三列：重量程序运⾏结果为：待改善。
