当前位置：首页 > news >正文

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

news 2026/4/15 23:17:54

今天分享一下连续背包问题的贪心算法

题目：连续背包问题是这样定义的：给定一个总承重量为 W 的背包和 n 件物品的集合 S={s1,⋯,sn}，其中第 i 件物品有其重量 wi 和价值 vi。如果将第 i 件物品 si 的 xi 部分（xi∈[0,1]）放入背包，则放入的重量为 xi⋅wi，放入的价值为 xi⋅vi。要求一种分派方案 x=(x1,⋯,xn)，在满足约束条件 R: Σi=1nxi⋅wi≤W（即装入的物品总重量不超过背包承重）的前提下，使优化函数 f(x)=Σi=1nxi⋅vi 取极大值（即装入的物品总价值最大）。

本题就请你实现解决这个问题的贪心算法。

输入格式：
输入首先在第一行中给出正整数 n（≤1000）和正实数 W（≤500）。随后两行各给出 n 个不超过 2000 的正实数，分别为 n 件物品的重量和价值，即第一行第 i 个数字表示第 i 件物品的重量，第二行对应位置表示其价值。同行数字间以空格分隔。

输出格式：
首先在第一行输出装入物品的最大总价值；随后一行输出最优分派方案的分量 (x1,⋯,xn)。要求输出小数点后 2 位。简单起见，每个分量后面跟一个空格。

输入样例：
5 11.0
1 2 5 6 7
1 6 18 22 28

输出样例：
42.67
0.00 0.00 0.00 0.67 1.00

#include <stdio.h>

int main(){
int n;//根据题目，首先定义一个int类型的n(题目中n < 1000所以int就够用了)
scanf("%d",&n);//读取n
double w;/*题目上说w是正实数所以用float或者double，一般来说float就行，我怕
数据太大所以就用的double,我个人感觉对于实数，除了题目要求之外，最好都用 double*/
scanf("%lf",&w);//读取w
double 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大的就赋值给max
index = 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;//能全部放进去所以找个物品对于自己的权重为1
cnt += 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.h>

int 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;
}