File FractionalKnapsack.h

↰ Parent directory (ADS/optimization)

The real (fractional) knapsack of section 14.1: a fraction x_i in [ 0 , 1 ] of each object, of largest profit :math:` sum_i p_i x_i ` and volume :math:` sum_i v_i x_i leq C `.

Definition (ADS/optimization/FractionalKnapsack.h)

Detailed Description

The greedy choice by decreasing specific profit :math:` p_i / v_i ` is optimal: the most profitable objects per unit of volume go in whole, the next one in part, the others not; O( n log n ) time for the sort. By decreasing profit or by increasing volume it is not, and neither is any of them for the 0-1 knapsack (exercise 14.1).

The contracts [see File Contract.h]: profits and volumes of the same objects, the volumes positive, the profits and the capacity not negative; the fractions are in [ 0 , 1 ] and fill at most the capacity. The operations are defined in FractionalKnapsack.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 14.1, https://algoritmicamente.it/materiali/libro/capitoli/cap14.pdf

    1. Dantzig, Discrete-variable extremum problems, Operations Research 5(2), 266-288, 1957, doi:10.1287/opre.5.2.266

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions