Page 223 - Bkhargava_-_Grokaem_algoritmy
P. 223

222    Глава 9.  Динамическое программирование


        предмета. Как решить такую задачу методом динамического программи­
        рования?

        Ответ: никак. В решении, полученном методом динамического програм­
        мирования, вы либо берете предмет, либо не берете. Алгоритм не преду­
        сматривает возможность взять половину предмета.

        Однако проблема легко решается с помощью жадного алгоритма! Сна­
        чала вы берете самый ценный предмет -      настолько большую его часть,
        насколько возможно. Когда самый ценный предмет будет исчерпан, вы
        берете максимально возможную часть следующего по ценности предмета
        ит.д .
        Допустим, вы можете выбирать из следующих товаров.


                                   .
                             ~  f7  е
                                           1

                              КМ НО А      D..M        РИС.
                             .$&/ФУНТ     .$~/ФУНТ    .$2./ФУНТ




        Фунт киноа стоит дороже, чем фунт любого другого товара. А раз так - на­
        бирайте столько киноа, сколько сможете унести! И если вам удастся набить
        им свой рюкзак, то это и будет лучшее из возможных решений.


                                             PIOKJAK
                                              НАБИТ
                                              КИНОА










        Если киноа кончится, а в рюкзаке еще остается свободное место, возьмите
        следующий по ценности товар и т. д.






                                                         www.trk.kg
   218   219   220   221   222   223   224   225   226   227   228