c++ - 使用贪心算法没有得到所需的背包问题输出
问题描述
我正在尝试对分数背包问题实施一种贪婪的方法。
输入格式为:输入的第一行包含物品的数量和背包的容量。下一行定义了项目的值和权重。第 - 行包含整数和 - 第 - 项的值和权重,分别。
输出将是最大值。
我已经用 C++ 实现了这个算法
#include <iostream>
#include <vector>
using std::vector;
double get_optimal_value(int capacity, vector<int> weights, vector<int> values, int n) {
double value = 0.0;
double A[] {};
int amt = 0;
for (int i = 0; i < n; i++) {
if (capacity = 0){
break;
}
else {
amt = std::min(weights[i], capacity);
weights[i] -= amt;
A[i] = A[i] + amt;
value = value + amt*(values[i]/weights[i]);
capacity -= amt;
}
}
return value;
}
int main() {
int n;
int capacity;
std::cin >> n >> capacity;
vector<int> values(n);
vector<int> weights(n);
for (int i = 0; i < n; i++) {
std::cin >> values[i] >> weights[i];
}
double optimal_value = get_optimal_value(capacity, weights, values, n);
std::cout.precision(10);
std::cout << optimal_value << std::endl;
return 0;
}
当我输入一些值时,我得到的输出为 0
3 50
60 20
100 50
120 30
0
任何有关这方面的指导都会非常有帮助。提前谢谢你
解决方案
推荐阅读
- mysql - 使用 SQL 将数据批量插入到空(但现有)记录中
- java - 如何在 apache poi 中使用 2 行的单元格引用
- arrays - 如何从角度formData在rest api中以字符串或int数据发布列表数据
- amazon-web-services - 来自 AWS lambda 的内存中查找
- apache - Apache RewriteCond 比较 TIME
- python - CircuitPython 将元组作为参数传递,错误需要 Integer
- r - XML:从 xml 查询中提取所有时间序列
- dataframe - PySpark 过滤数据框并将数据框写入 mysql 数据库
- label - 如何将标签四舍五入到小数点后两位?
- bash - 使用 cat 从 linux os 读取文件并忽略换行符