[C++] 부분 배낭 문제 (Fractional Knapsack Problem) / 그리디 알고리즘

#include<queue>
#include<iostream>
#include<algorithm>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

int main() {
	double data[5][2] = { {10, 10}, {15, 12}, {20, 10}, {25, 8}, {30, 5} };
	double temp[2];
	double total_value = 0.0;
	double capacity = 30.0;
	vector<vector<double>> details;

	for(int i=0; i<4; i++)
		for (int j = 0; j < 4-i; j++) {
			if (data[j][1] / data[j][0] < data[j + 1][1] / data[j + 1][0]) {
				temp[0] = data[j][0];
				temp[1] = data[j][1];
				data[j][0] = data[j+1][0];
				data[j][1] = data[j+1][1];
				data[j+1][0] = temp[0];
				data[j+1][1] = temp[1];
			}
		}

	for (auto *elem : data) {
		vector<int> temp(3, 0);
		if (capacity >= elem[0]) {
			capacity -= elem[0];
			total_value += elem[1];
			details.push_back({elem[0], elem[1], 1});
		}
		else {
			double fraction = capacity / elem[0];
			capacity -= elem[0] * fraction;
			total_value += elem[1] * fraction;
			details.push_back({ elem[0], elem[1], fraction });
			break;
		}
	}

	cout << total_value << '\n' ;

	for (auto elem : details) {
		cout << elem[0] << " " << elem[1] << " " << elem[2] << '\n';
	}

}