算法(背包问题)
/*** @file Fractional_Knapsack_Problem.c++
* @author Luke Tebo (luketebo.ycs@gmail.com)
* @brief
* @version 0.1
* @date 2022-05-24
*
* @copyright Copyright (c) 2022
*
* 输入： n个物品组成的集合O, 每个物品有两个属性vi 和 pi, 分别表示体积和价格
* 背包容量为C
* 输出： 背包中物品的最大价值
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Fractional_Knapsack_Problem
{
private:
/* data */
public:
Fractional_Knapsack_Problem(/* args */);
~Fractional_Knapsack_Problem();
void knapsack(vector<float> &v, vector<float> &p, int c);
};
Fractional_Knapsack_Problem::Fractional_Knapsack_Problem(/* args */)
{
}
Fractional_Knapsack_Problem::~Fractional_Knapsack_Problem()
{
}
void Fractional_Knapsack_Problem::knapsack(vector<float> &v, vector<float> &p, int c)
{
// v : 体积
// p : 价格都是有序的(假设)
// c : 背包容量
int size = v.size();
int result = 0; // 背包中物品的最大价值
vector<float> average(5, 0); // 分数
for (int i = 0; i < average.size(); i++)
{
average.push_back(v / p);
}
for (int i = 0; i < average.size(); i++)
{
cout << average << " ";
}
cout << endl;
for (int i = 0; i < size; i++)
{
if (v <= c)
{
result += p;
c -= v;
}
else
{
result += p * c / v;
c = 0;
}
}
cout << result << endl;
}
int main()
{
vector<float> v = {5, 4, 3, 2, 1}; // 体积
vector<float> p = {1, 2, 3, 4, 5}; // 价格
Fractional_Knapsack_Problem f;
f.knapsack(v, p, 5);
return 0;
}
页:
[1]