分数背包问题
作者:
张妈
,
2024-01-12 16:05:42
,
所有人可见
,
阅读 49
//
// Created by asdfsa on 2024/1/12.
//
#include <bits/stdc++.h>
int main () {
// 假设的质量和重量1数组
std::vector<int> value = {1,2,3,4,5};
std::vector<int> weight = {2,1,5,3,1};
// 假设的背包容量
double bagWeight = 5.0;
// 编写一个简单的冒泡排序 使用单位质量来对 物品数组进行排序, 进行倒序排序
// 从而可以得到一个 通过单位质量来进行排序的数组, 这个数组的的第一位的物品编号和价值就是对应的下标0,他也是单位价值最高的
for (int i = 0; i < value.size()-1; ++i) {
for (int j = 0; j < value.size()-1-i; ++j) {
if (((double)value[j]) /weight[j] < ((double)value[j+1]) /weight[j+1]) {
std::swap(value[j+1], value[j]);
std::swap(weight[j+1], weight[j]);
}
}
}
// 这里就对进行遍历已经倒序的数组了, 累加 , 如果当物品装满了便可以使用分数来加分数层面上的物品单位价值
double sumV =0, sumW=0;
for (int i = 0; i < value.size(); ++i) {
if (sumW + weight[i] <= bagWeight) {
sumW += weight[i];
sumV += value[i];
}else {
// 只能装下分数的容量
sumV +=(bagWeight-sumW) * (value[i]/weight[i]);
break;
}
}
std::cout<< sumV << std::endl;
}
//定义一个结构来存储物品的重量、价值及其单位价值。
//计算每个物品的单位价值并按照这个值进行降序排序。
//遍历排序后的物品列表,对每个物品执行:
//如果背包可以装下整个物品,则将其加入背包,并更新背包的剩余容量。
//如果背包不能装下整个物品但还有空间,则装入背包能装下的部分,更新背包容量,然后结束循环。
//计算背包中物品的总价值。