【无标题】《背包塞不下？贪心算法教你“碎尸万段”也能价值最大（附C代码）》

今天分享一下连续背包问题的贪心算法题目连续背包问题是这样定义的给定一个总承重量为 W 的背包和 n 件物品的集合 S{s1​,⋯,sn​}其中第 i 件物品有其重量 wi​ 和价值 vi​。如果将第 i 件物品 si​ 的 xi​ 部分xi​∈[0,1]放入背包则放入的重量为 xi​⋅wi​放入的价值为 xi​⋅vi​。要求一种分派方案 x(x1​,⋯,xn​)在满足约束条件 R: Σi1n​xi​⋅wi​≤W即装入的物品总重量不超过背包承重的前提下使优化函数 f(x)Σi1n​xi​⋅vi​ 取极大值即装入的物品总价值最大。本题就请你实现解决这个问题的贪心算法。输入格式输入首先在第一行中给出正整数 n≤1000和正实数 W≤500。随后两行各给出 n 个不超过 2000 的正实数分别为 n 件物品的重量和价值即第一行第 i 个数字表示第 i 件物品的重量第二行对应位置表示其价值。同行数字间以空格分隔。输出格式首先在第一行输出装入物品的最大总价值随后一行输出最优分派方案的分量 (x1​,⋯,xn​)。要求输出小数点后 2 位。简单起见每个分量后面跟一个空格。输入样例5 11.01 2 5 6 71 6 18 22 28输出样例42.670.00 0.00 0.00 0.67 1.00#include stdio.hint main(){int n;//根据题目首先定义一个int类型的n(题目中n 1000所以int就够用了)scanf(%d,n);//读取ndouble w;/*题目上说w是正实数所以用float或者double一般来说float就行我怕数据太大所以就用的double,我个人感觉对于实数除了题目要求之外最好都用 double*/scanf(%lf,w);//读取wdouble a1[n],a2[n];//按题目要求弄2个实数数组double A[n];/*这个数组我是用来存每个物品每一单位的价值因为题目要求要最大价值所以肯定是优先把一单位价值最高的存进去*/for(int i 0;i n;i){scanf(%lf,a1[i]);//读取物体体积}for(int i 0;i n;i){scanf(%lf,a2[i]);//读取物体重量}for(int i 0;i n;i){A[i] a2[i] / a1[i];//计算每个物体每单位的价值}double cnt 0,result 0;/*cnt是在把物品装进背包时记录背包装了多少result是当前装入背包物品的总价值*/int index 0;//现在解释不太好理解index我在下面在解释double s[n];//根据题目要求我们需要记录装入背包物品的对自己本身的权重for(int i 0;i n;i){s[i] 0;//初始化}while(cnt w){//只要背包没装满就接着装double max 0;/*弄一个max上面不是说过要找每个单位价值最大的吗max就是用来存储物品中价值最大的*/for(int i 0;i n;i){/*因为我们不知道物品中单位价值最大的是哪个所以需要弄个循环找一下也可以排序因为我感觉c语言中排序又麻烦又费时所以就直接弄个循环找最大值了*/if(max A[i]){max A[i];//找到比max大的就赋值给maxindex i;//记录一下当前数组里单位价值最大的物品的下标}}A[index] 0;/*因为我们等会给这个物品装入背包后放入下一个物品时如果不给之前最大的哪个改小一点那最大值max就一直会是这个物品可是这个物品我们已经装入背包了已经没有了所以要给他的单位价值改为0*/if(max 0){/*如果我们找最大值max找了一圈max还是等于0就证明物品全放进背包了这种情况就是背包的容量大于或等于所有物品的体积就是说背包可以把所有的物品都装进去*/break;//所以cnt会一直满足循环条件所以要加个break跳出循环}/*我们找到单位价值最大的物品后把他放入背包有2种情况一个是可以全部放进去一个是只能放进去一部分*/if(a1[index] w - cnt){//这个就是可以全部放进去的s[index] 1.0;//能全部放进去所以找个物品对于自己的权重为1cnt a1[index];//把这个物品放进去把背包现在装了多少东西更新一下result a2[index];//当前背包物品的价值也更新一下}else{result ((w - cnt) / a1[index]) * a2[index];/*这个就是只能放进去一部分放进去那部分的价值加上背包之前的价值*/s[index] (w - cnt) / a1[index];//放进去那部分物品对于本身的权重cnt w;//背包都不能把物品整个进去了不就证明背包满了所以我们把背包容量赋值给cnt}}printf(%.2f\n,result);//输出背包总价值for(int i 0;i n;i){printf(%.2f ,s[i]);//输出每一个物品装进背包的权重}return 0;}下面是不要注释的#include stdio.hint main(){int n;scanf(%d,n);double w;scanf(%lf,w);double a1[n],a2[n];double A[n];for(int i 0;i n;i){scanf(%lf,a1[i]);}for(int i 0;i n;i){scanf(%lf,a2[i]);}for(int i 0;i n;i){A[i] a2[i] / a1[i];}double cnt 0,result 0;int index 0;double s[n];for(int i 0;i n;i){s[i] 0;}while(cnt w){double max 0;for(int i 0;i n;i){if(max A[i]){max A[i];index i;}}A[index] 0;if(max 0){break;}if(a1[index] w - cnt){s[index] 1.0;cnt a1[index];result a2[index];}else{result ((w - cnt) / a1[index]) * a2[index];s[index] (w - cnt) / a1[index];cnt w;}}printf(%.2f\n,result);for(int i 0;i n;i){printf(%.2f ,s[i]);}return 0;}