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,
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 */
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.
0 kommentar(er)
