Comments 9
Казалось бы при чем тут сгоревшие у костра ботинки…
d=b2/a не является верным решением.
Пример:
Есть рюкзак грузоподъемности 2 и три предмета: один — ценности 2 и веса 2, а два других — ценности 1,01 и веса 1 каждый.
D первого предмета 2, второго и третьего — 1,01.
Таким образом, Ваше решение возьмет первый предмет, и, таким образом, обеспечит уровень полезности 2, вместо оптимального 2,02.
И еще: задача о рюкзаке не является NP-сложной, если все веса целые и ограничены хоть какой-то константой. Кроме того, часто используют непрерывную задачу о рюкзаке — в ней можно взять половину предмета, и, очевидно, работает жадность a/b.
Автор, пожалуйста, учите алгоритмы прежде, чем писать о них.
Пример:
Есть рюкзак грузоподъемности 2 и три предмета: один — ценности 2 и веса 2, а два других — ценности 1,01 и веса 1 каждый.
D первого предмета 2, второго и третьего — 1,01.
Таким образом, Ваше решение возьмет первый предмет, и, таким образом, обеспечит уровень полезности 2, вместо оптимального 2,02.
И еще: задача о рюкзаке не является NP-сложной, если все веса целые и ограничены хоть какой-то константой. Кроме того, часто используют непрерывную задачу о рюкзаке — в ней можно взять половину предмета, и, очевидно, работает жадность a/b.
Автор, пожалуйста, учите алгоритмы прежде, чем писать о них.
Ваш контр-пример неправильный. Скорее всего, это вызвано тем, что у автора в статье путаница с порядком сортировки — в начале a/b, потом b/2 заменяется на b^2/a. Правильнее было бы привести контр-пример с предметами, ценность которых меньше единицы. Например пары (a, b), (1, 1), (0.5, 0.6), (0.5, 0.6) и ограничение на сумму а = 1
Но в целом, вы правы.
Но в целом, вы правы.
Хороший пример. Если в наборе есть элементы сумма весов меньше или равна веса какого-то элемента, и, соответственно, сумма ценностей больше или равна ценности элемента, то алгоритм даст неверный результат. Вопрос в том, как выловить эти случаи. Это уже отдельная задача, над которой стоит подумать. Существуют ли еще варианты наборов, при которых этот способ даст неверное решение?
И тут мы возводим все исходные 'a' в квадрат и получаем такую же оценку (b^2/a^2 == b/a) как и в первом случае. Что будем делать?
UFO just landed and posted this here
Sign up to leave a comment.
Немного об укладке рюкзака