Knapsack problem/Unbounded: Difference between revisions

</pre>

=={{header|C++}}==

<syntaxhighlight lang="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;

}

</syntaxhighlight>

{{ out }}

<pre>

Item Chosen Number Value Weight Volume

----------- ------ ----- ------ ------

panacea 9 27000 2.70 0.23

gold 11 27500 22.00 0.02

----------- ------ ----- ------ ------

2 items 20 54500 24.70 0.25