Rosetta Code

Knapsack problem/Unbounded: Difference between revisions

Page Discussion

Knapsack problem/Unbounded (view source)

Revision as of 23:12, 17 January 2009

415 bytes added ,  15 years ago
→‎{{header|C}}
Line 183:
{{trans|Fortran}}
<c>#include <stdio.h>
 
double min(double a, double b) {
return a < b ? a : b;
Line 190:
struct Bounty {
int value;
double weight, volume;
double volume;
};
Line 198 ⟶ 197:
gold = {2500, 2.0, 0.002},
sack = { 0, 25.0, 0.25 },
current, best;
#define CALC(V) current.V = inpanacea * panacea.V + jnichor * ichor.V + kngold * gold.V
 
 
int main() {▼
int i, j, k;
double total_weight, total_volume;
int max_panacea, max_ichor, max_gold, max_value = 0;
int n[3];▼
▲int main(void) {
max_panacea = min(sack.weight / panacea.weight, sack.volume / panacea.volume);▼
int npanacea, nichor, ngold, max_panacea, max_ichor, max_gold;
max_ichor = min(sack.weight / ichor.weight, sack.volume / ichor.volume);▼
▲ int nbest_amounts[3];
max_gold = min(sack.weight / gold.weight, sack.volume / gold.volume);
for (ibest.value = 0; i <= max_panacea; i++) {
▲ max_panacea = (int)min(sack.weight / panacea.weight, sack.volume / panacea.volume);
for (j = 0; j <= max_ichor; j++) {▼
▲ max_ichor = (int)min(sack.weight / ichor.weight, sack.volume / ichor.volume);
for (k = 0; k <= max_gold; k++) {
max_gold = (int)min(sack.weight / gold.weight, sack.volume CALC(value/ gold.volume);
 
CALC(weight);▼
for (npanacea = 0; npanacea <= max_panacea; npanacea++) {
CALC(volume);
▲ for (jnichor = 0; jnichor <= max_ichor; jnichor++) {
if (current.weight > sack.weight || current.volume > sack.volume)
for (ngold = 0; ngold <= max_gold; ngold++) continue;{
if (current.value >= max_value)npanacea {* panacea.value + nichor * ichor.value + ngold * gold.value;
current.weight = npanacea * max_valuepanacea.weight =+ currentnichor * ichor.weight + ngold * gold.valueweight;
current.volume = npanacea * total_weightpanacea.volume =+ currentnichor * ichor.volume + ngold * gold.weightvolume;
total_volume = current.volume;
if (current.value > best.value n[0]&& current.weight <= i;sack.weight &&
n[1]current.volume <= j;sack.volume) {
n[2]best.value = kcurrent.value;
▲ CALC( best.weight = current.weight);
best.volume = current.volume;
best_amounts[0] = npanacea;
best_amounts[1] = nichor;
best_amounts[2] = ngold;
}
}
Line 233 ⟶ 230:
}
printf("Maximum value achievable is %d\n", best.value);
printf("This is achieved by carrying (one solution) %d panacea, %d ichor and %d gold\n",
best_amounts[0], best_amounts[1], best_amounts[2]);
printf("The weight to carry is %4.1f and the volume used is %5.3f\n", best.weight, best.volume);
max_value,
 
n[0], n[1], n[2],
return 0;
total_weight, total_volume);
}</c>
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/89612"