Knapsack problem/Unbounded: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Minor tidy) |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 830:
take(Ichor): 0
take(Gold): 11
</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
</pre>
Line 1,577 ⟶ 1,675:
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
The weight to carry is 25.0 and the volume used is 0.247
=={{header|FreeBASIC}}==
{{trans|PureBASIC}}
<syntaxhighlight lang="vb">#define min(a, b) iif((a) < (b), (a), (b))
Dim As Single totalPeso, totalVolumen
Dim As Integer maxPanacea, maxIchor, maxGold, maxValor
Dim As Integer i, j ,k
Dim As Integer n(2)
Type Bounty
articulo As String*7
valor As Integer
peso As Single
volumen As Single
End Type
Dim item(1 To 5) As Bounty => { _
("panacea", 3000, 0.3, 0.025), ("ichor", 1800, 0.2, 0.015), _
("gold", 2500, 2.0, 0.002), ("sack", 0, 25.0, 0.25 )}
maxPanacea = min(item(4).peso/item(1).peso, item(4).volumen/item(1).volumen)
maxIchor = min(item(4).peso/item(2).peso, item(4).volumen/item(2).volumen)
maxGold = min(item(4).peso/item(3).peso, item(4).volumen/item(3).volumen)
For i = 0 To maxPanacea
For j = 0 To maxIchor
For k = 0 To maxGold
item(0).valor = k*item(3).valor + j*item(2).valor + i*item(1).valor
item(0).peso = k*item(3).peso + j*item(2).peso + i*item(1).peso
item(0).volumen = k*item(3).volumen + j*item(2).volumen + i*item(1).volumen
If item(0).peso > item(4).peso Or item(0).volumen > item(4).volumen Then
Continue For
End If
If item(0).valor > maxValor Then
maxValor = item(0).valor
totalPeso = item(0).peso
totalVolumen = item(0).volumen
n(0) = i: n(1) = j: n(2) = k
End If
Next k
Next j
Next i
Print "Maximum valor achievable is "; Str(maxValor)
Print "This is achieved by carrying "; Str(n(0));
Print " panacea, "; Str(n(1)); " ichor and "; Str(n(2)); " gold items."
Print "The peso to carry is "; Str(totalPeso);
Print " and the volume used is "; Str(totalVolumen)
Sleep</syntaxhighlight>
{{out}}
<pre>Maximum valor achievable is 54500
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
The peso to carry is 25 and the volume used is 0.247</pre>
=={{header|Go}}==
Line 4,152 ⟶ 4,305:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
class Item {
Line 4,238 ⟶ 4,391:
----------- ------ ----- ------ ------
2 items 20 54500 24.7 0.25
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">func Min(A, B);
real A, B;
return fix(if A < B then A else B);
int Panacea, Ichor, Gold, Panacea_, Ichor_, Gold_, Val, Max;
real Weight, Volume;
[Max:= 0;
for Panacea:= 0 to Min(25.0/0.3, 0.25/0.025) do
[for Ichor:= 0 to Min(25.0/0.2, 0.25/0.015) do
[for Gold:= 0 to Min(25.0/2.0, 0.25/0.002) do
[Val:= Panacea*3000 + Ichor*1800 + Gold*2500;
Weight:= float(Panacea)*0.3 + float(Ichor)*0.2 + float(Gold)*2.0;
Volume:= float(Panacea)*0.025 + float(Ichor)*0.015 + float(Gold)*0.002;
if Val>Max and Weight<=25.0 and Volume<= 0.25 then
[Max:= Val;
Panacea_:= Panacea; Ichor_:= Ichor; Gold_:= Gold;
];
];
];
];
Text(0, "The traveler carries ");
IntOut(0, Panacea_); Text(0, " vials of panacea, ");
IntOut(0, Ichor_); Text(0, " ampules of ichor, and ");
IntOut(0, Gold_); Text(0, " bars of gold"); CrLf(0);
Text(0, "for a maximum value of "); IntOut(0, Max); CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
The traveler carries 0 vials of panacea, 15 ampules of ichor, and 11 bars of gold
for a maximum value of 54500
</pre>
| |||