Jump to content

Knapsack problem/Unbounded: Difference between revisions

Knapsack problem/Unbounded (view source)

Revision as of 13:47, 17 January 2009

151 bytes added ,  15 years ago
→‎{{header|C}}
Line 183:
{{trans|Fortran}}
<c>#include <stdio.h>
 
double min(double a, double b) {
#define MIN(a,b) ( ((a)<(b)) ? (a) : (b) )
return a < b ? a : {b;▼
 
}
struct Bounty {
int value;
double weight;
double volume;
};
 
double totalWeight, totalVolume;
int maxPanacea, maxIchor, maxGold, maxValue = 0;
int n[3];▼
 
struct 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 },
current;
 
#define CALC(V) current.V = i * panacea.V + j * ichor.V + k * gold.V
 
int main()▼
{
int i, j, k;▼
 
▲int main() {
maxPanacea = MIN( sack.weight / panacea.weight, sack.volume / panacea.volume );▼
▲ int i, j, k;
maxIchor = MIN( sack.weight / ichor.weight, sack.volume / ichor.volume );▼
double total_weight, total_volume;
maxGold = MIN( sack.weight / gold.weight, sack.volume / gold.volume );▼
int max_panacea, max_ichor, max_gold, max_value = 0;
▲ int n[3];
for(i=0; i <= maxPanacea ; i++ )
{
▲ maxPanacea max_panacea = MINmin( sack.weight / panacea.weight, sack.volume / panacea.volume );
for(j=0; j <= maxIchor ; j++ )
▲ maxIchor max_ichor = MINmin( sack.weight / ichor.weight, sack.volume / ichor.volume );
{▼
▲ maxGold max_gold = MINmin( sack.weight / gold.weight, sack.volume / gold.volume );
for(k=0; k <= maxGold ; k++ )
{▼
for (i = 0; i <= max_panacea; CALC(valuei++); {
for (j = 0; j CALC(weight)<= max_ichor; j++) {
for CALC(volume)k = 0; k <= max_gold; k++) {
if ( CALC( current.weight > sack.weight value) ||;
CALC( current.volume > sack.volume weight) ) continue;
if ( current.value > maxValue CALC(volume);
if (current.weight > sack.weight || current.volume > sack.volume)
▲ {
maxValue = current.value continue;
if totalWeight = (current.weight;value > max_value) {
totalVolume max_value = current.volumevalue;
n[0] = i; n[1] = j; n[2]total_weight = kcurrent.weight;
} total_volume = current.volume;
} n[0] = i;
n[1] = j;
n[2] = k;
}
▲ { }
▲ { }
}
}
printf("Maximum value achievable is %d\n"▼
"This is achieved by carrying (one solution) %d panacea, %d ichor and %d gold\n"
▲ printf("Maximum value achievable is %d\n"
"ThisThe isweight achievedto bycarry carryingis %d4.1f panacea,and %dthe ichorvolume andused %dis gold%5.3f\n",
max_value,
"The weight to carry is %4.1f and the volume used is %5.3f\n",
maxValue n[0], n[1], n[2],
n[0], n[1] total_weight, n[2],total_volume);
totalWeight, totalVolume);
}</c>
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/89611"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information