86 lines
2.4 KiB
C++
86 lines
2.4 KiB
C++
#include <algorithm>
|
|
#include <cmath>
|
|
#include <cstdint>
|
|
#include <iomanip>
|
|
#include <iostream>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
struct Item {
|
|
std::string name;
|
|
int32_t value;
|
|
double weight;
|
|
double volume;
|
|
};
|
|
|
|
const std::vector<Item> items = {
|
|
Item("panacea", 3000, 0.3, 0.025),
|
|
Item("ichor", 1800, 0.2, 0.015),
|
|
Item("gold", 2500, 2.0, 0.002)
|
|
};
|
|
constexpr double MAX_WEIGHT = 25.0;
|
|
constexpr double MAX_VOLUME = 0.25;
|
|
|
|
std::vector<int32_t> count(items.size(), 0);
|
|
std::vector<int32_t> best(items.size(), 0);
|
|
int32_t best_value = 0;
|
|
|
|
void knapsack(const uint64_t& i, const int32_t& value, const double& weight, const double& volume) {
|
|
if ( i == items.size() ) {
|
|
if ( value > best_value ) {
|
|
best_value = value;
|
|
best = count;
|
|
}
|
|
return;
|
|
}
|
|
|
|
int32_t measure1 = (int32_t) std::floor( weight / items[i].weight );
|
|
int32_t measure2 = (int32_t) std::floor( volume / items[i].volume );
|
|
int32_t measure = std::min(measure1, measure2);
|
|
count[i] = measure;
|
|
|
|
while ( count[i] >= 0 ) {
|
|
knapsack(
|
|
i + 1,
|
|
value + count[i] * items[i].value,
|
|
weight - count[i] * items[i].weight,
|
|
volume - count[i] * items[i].volume
|
|
);
|
|
count[i]--;
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
knapsack(0, 0, MAX_WEIGHT, MAX_VOLUME);
|
|
std::cout << "Item Chosen Number Value Weight Volume" << std::endl;
|
|
std::cout << "----------- ------ ----- ------ ------" << std::endl;
|
|
int32_t item_count = 0;
|
|
int32_t number_sum = 0;
|
|
double weight_sum = 0.0;
|
|
double volume_sum = 0.0;
|
|
|
|
for ( uint64_t i = 0; i < items.size(); ++i ) {
|
|
if ( best[i] == 0 ) {
|
|
continue;
|
|
}
|
|
|
|
item_count++;
|
|
std::string name = items[i].name;
|
|
int32_t number = best[i];
|
|
int32_t value = items[i].value * number;
|
|
double weight = items[i].weight * number;
|
|
double volume = items[i].volume * number;
|
|
number_sum += number;
|
|
weight_sum += weight;
|
|
volume_sum += volume;
|
|
|
|
std::cout << std::setw(11) << name << std::setw(6) << number << std::setw(8) << value << std::fixed
|
|
<< std::setw(8) << std::setprecision(2) << weight
|
|
<< std::setw(8) << std::setprecision(2) << volume << std::endl;
|
|
}
|
|
|
|
std::cout << "----------- ------ ----- ------ ------" << std::endl;
|
|
std::cout << std::setw(5) << item_count << " items" << std::setw(6) << number_sum << std::setw(8) << best_value
|
|
<< std::setw(8) << weight_sum << std::setw(8) << volume_sum << std::endl;
|
|
}
|