← Lab · Chapter: Approximation algorithms for the knapsack problem

0/1 KP: greedy, Ext-Greedy, H² and FPTAS

The approximation algorithms of the chapter step by step, with the ratio z(I)/A(I); in the FPTAS the scaled profits and the DP by profits. Choose the algorithm; in the FPTAS the slider ε changes the accuracy; ◀ ▶ one step at a time, «Run» to watch them all; the «Instance» menu and «Edit…» change the instance.