实验五：贪心算法求解背包问题 一、 实验内容 有一个承重为 W的背包和 n个物品，它们各自的重量和价值分别是 wi 和 vi （1<=i<=n），设 求这些物品中最有价值的一个子集。如果每次选择某 一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次 可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。   W w i n i  1 二、 算法思想 首先计算出物品单位重量的价值 vi/wi，并排序，依贪婪策略，从物品中选择 可装入背包的 vi/wi 值最大的物品。若该物品装入背包后，背包中物品总重量未超 过背包最大承重 m，则选择单位重量价值次之的物品装入背包，依次策略进行下去， 直到背包装满为止。 三、 实验过程（C++） #include using namespace std; //n 表示背包可以存放物品的种类 //指针 p 指向存放物品价值的数组 //指针 q 指向存放物品重量的数组 void sort(int n,float *p,float *q) { int i; int j; for(i=0;im) break; *(x+i)=1;//可以存放该物品时，置 1 m-=*(w+i);//放入后,背包的容量减少 } //当此时背包的容量不够存放整个物品的情况时，存放一部分 if(i

*(x+i)=m/(*(w+i)); if(*(x+i)!=1) *(x+i)=0; } int main() { int m ,n,i; cout<<"输入背包容量："<>m; cout<<"输入物品种类："<>n; float *w=new float[n]; float *v=new float[n]; float *x=new float[n]; cout<<"输入各种物品的重量："<>w[i];//各种物品的重量 cout<<"输入各种物品的价值："<>v[i];//各种物品的价值 for(i=0;i

物品容量内容:26 15 23 物品价值内容:18 10 15 物品存放情况:1 1 五、 算法复杂度分析 0 Tsort = O(在此处键入公式。nlogn)； 时间复杂度为 O（n2）； Tf（for 循环复杂度为） =n2； T = sort + Tf = O(nlogn) + O(n2) = O(n2).