5.8.3 Непрерывная задача о рюкзаке

Условия те же самые, с той лишь разницей, что предметы можно де- лить на части, то есть вор может украсть часть одного предмета. В такой задаче применим жад- ный алгоритм, описанный выше ( с той лишь разницей, что если очередной предмет из отсортиро- ванного списка предметов не по- мещается в рюкзак целиком, то о т него вор берет ту часть, что п омещается в рюкзак). Таким обр- азом, если бы мы рассматривал- и тот же пример из трех предмет- ов 1  ($60, 10 кг), 2  ($100, 20 кг ), 3  ($120, 30 кг), вор бы взял ц еликом первый и второй из них; о сталось свободным 20 кг в рюкз- аке; вор отделил бы 2/3 части от т ретьего предмета (что составит 20 кг) и забрал в сумме $60+$100 + 2/3*$120 = $240. Для непрерывной задачи о рюкзаке жадный алгоритм будет давать оптимальное решение.