ticketsnax.blogg.se

Contoh program c fractional knapsack
Contoh program c fractional knapsack




Printf("of item %u (weight %u value %u)\n", i, weights, values) Unsigned int *knapsack, size_t len, unsigned int capacity) Unsigned int fractional_knapsack(const unsigned int *values, const unsigned int *weights,

contoh program c fractional knapsack

Unsigned int vw2 = item2->value / item2->weight Unsigned int vw1 = item1->value / item1->weight Int compare_items(const item *item1, const item *item2) * Compare items by greater value / weight */

contoh program c fractional knapsack

I have assumed that value / weight is always a whole number for simplicity, but one could easily modify it for continuous values. When the knapsack cannot contain it we enough of it to fill the remaining capacity and so are at the last item. Only the last item can need to be broken up because the sorting by value / weight guarantees that the current item is the optimum one to take, so we should take as much as it as we can, which until the knapsack cannot contain it, will be the whole item.

contoh program c fractional knapsack

  • Take as much as you can of each item until the knapsack is at capacity.
  • Sort the items in decreasing order of value / weight.
  • This last relaxation of the usual conditions means that we can use a greedy algorithm to solve the problem: The fractional knapsack problem is to fill a knapsack of given capacity with unique items of a given weight and value so as to maximise the value of the knapsack, with breaking items up being permitted.






    Contoh program c fractional knapsack