Совсем детский вопрос или "Задача о сдаче"

Тема в разделе "WASM.A&O", создана пользователем Enchantner, 18 дек 2010.

  1. Enchantner

    Enchantner New Member

    Публикаций:
    0
    Регистрация:
    29 июл 2008
    Сообщения:
    23
    Знаю, что задача "дать сдачу минимальным числом монет заданных номиналов" - классическая, даже школьная задача по динамическому программированию. Но уж очень хочется вникнуть, прорешать такие задачи самому, потому что опыта по алгоритмам катастрофически не хватает.

    Сейчас программа выглядит так:
    Код (Text):
    1. #include <iostream>
    2. #include <vector>
    3. #include <limits>
    4.  
    5. template <typename _T, typename _V>
    6. std::vector<_T> & operator,(std::vector<_T> & _vec, _V _elem) {
    7.     _vec.push_back(_elem);
    8.     return _vec;
    9. }
    10.  
    11. std::vector<int> fillDefault() {
    12.     std::vector<int> v;
    13.     return (v, 1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000);
    14. }
    15.  
    16. const unsigned short int C = 10;
    17.  
    18. int main() {
    19.     using std::vector;
    20.     vector<int> nominal = fillDefault();
    21.     int i, j;
    22.    
    23.     int changesize = 0;
    24.     std::cin >> changesize;
    25.    
    26.     vector< vector<int> > changevals(changesize);
    27.    
    28.     for (int i=0; i<changesize; i++) {
    29.         changevals.push_back(vector<int>(C));
    30.         for (int j=0; j<C; j++) {
    31.             changevals[i].push_back(0);
    32.         }
    33.     }
    34.    
    35.     changevals[0][0] = 0;
    36.    
    37.    
    38.     for (i=1; i<=changesize; i++) {
    39.         for (j=0; j<C; j++) {
    40.             if (nominal[j] <= i) {
    41.                 changevals[i][j] = std::max(changevals[i][j], changevals[i - nominal[j]][j] + 1);
    42.                 //Here comes trouble
    43.             }
    44.            
    45.         }
    46.     }
    47.    
    48.     for (i=0; i<C; i++) {
    49.         std::cout << nominal[i] << ": " << changevals[changesize][i] << std::endl;
    50.     }
    51.    
    52.     return 0;
    53. }
    Считается по сути правильно, но косяки с тем, что нужно число монет меньшего достоинства сокращать числом монет большего достоинства, т.е. пять монет по рублю превращать в одну пятирублевую. Как сделать это классически правильно и получить верный результат? Хочется решить именно динамикой, без жадных алгоритмов.

    И да, я знаю, что это очень похоже на "задачу о рюкзаке" и всем прочем, пока просто не получилось до конца допилить. И это не курсовая студенческая, разбираюсь чисто для себя.

    Чтобы точнее описать мой способ решения - я использую для хранения результата двумерный массив длиной с введенное значение сдачи, а шириной с количество разных номиналов монет, чтобы на каждом этапе хранить число монет для каждого номинала.

    P.S. И не слишком ли извращенно я задал начальные значения вектору?
     
  2. baldr

    baldr New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    327
    Enchantner,

    В данном базисе оптимальное решение единственно. Надо представить сумму как линейную комбинацию базиса, и всё. Заковырки возникли бы в случае взаимной простоты номиналов (5==3+2 и т.д.).
     
  3. Enchantner

    Enchantner New Member

    Публикаций:
    0
    Регистрация:
    29 июл 2008
    Сообщения:
    23
    baldr
    Если честно, мало что понял. Как надо представить сумму? В чем проблема с взаимной простотой?
     
  4. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.615
    Адрес:
    Russia
    Enchantner
    если монеты образуют степени по одному основанию то формула хартли - если нет то пробуйте применить формулу шенона
     
  5. gorodon

    gorodon New Member

    Публикаций:
    0
    Регистрация:
    19 окт 2009
    Сообщения:
    301
    Enchantner
    Что-то вы намудрили... Известное решение:
    Код (Text):
    1.  int changesize = 12345;//-число, которое нужно представить минимальным набором из базиса
    2.  int basis[10] = {1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000};//базис
    3.  int out[10]   = {0,0,0,0,0,0,0,0,0,0};//представление changesize в базисе
    4.  int i;
    5.  while(changesize > 0)
    6.  {
    7.     for(i=10-1;i>=0;i--)
    8.     {
    9.        if((changesize-basis[i])>=0)
    10.        {
    11.           out[i]++;
    12.           changesize-=basis[i];
    13.           break;
    14.        }
    15.     }
    16.  }
    Я на скорую руку написал - можно еще оптимизировать...
     
  6. Enchantner

    Enchantner New Member

    Публикаций:
    0
    Регистрация:
    29 июл 2008
    Сообщения:
    23
    gorodon
    это, насколько я вижу, жадный алгоритм, а мне надо линамическое программирование. Ваш алгоритм далеко не всегда будет выдавать минимальное число монет.
     
  7. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.615
    Адрес:
    Russia
    Enchantner
    вообщем gorodon очень близок к истине - его алгоритм эквивалент переводу числа в другую систему исчисления, пусть даже с неравномерным ростом
     
  8. gorodon

    gorodon New Member

    Публикаций:
    0
    Регистрация:
    19 окт 2009
    Сообщения:
    301
    Enchantner
    всегда будет выдавать минимальное число монет. Я специально не оптимизировал его дабы была видна идея -
    брать сначала самые "крупные монеты"....
    Естественно, алгоритм можно оптимизировать:
    Код (Text):
    1. int changesize = 12345;//-число, которое нужно представить минимальным набором из базиса
    2.  int basis[10] = {1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000};//базис
    3.  int out[10]   = {0,0,0,0,0,0,0,0,0,0};//представление changesize в базисе
    4.  int i = 10-1;//changes!!!
    5.  while(changesize > 0)
    6.  {
    7.     for( ;i>=0;i--)//changes!!!
    8.     {
    9.        if((changesize-basis[i])>=0)
    10.        {
    11.           out[i]++;
    12.           changesize-=basis[i];
    13.           break;
    14.        }
    15.     }
    16.  }
    или вообще сделать однопроходным:

    Код (Text):
    1. int changesize = 12345;//-число, которое нужно представить минимальным набором из базиса
    2.  int basis[10] = {1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000};//базис
    3.  int out[10]   = {0,0,0,0,0,0,0,0,0,0};//представление changesize в базисе
    4.  
    5.     for(int i = 10-1;i>=0;i--)
    6.     {
    7.        int k = changesize/basis[i];
    8.        if(k>0)
    9.        {
    10.           out[i]+=k;
    11.           changesize-=k*basis[i];
    12.  
    13.           if(changesize==0)
    14.             break;
    15.        }
    16.     }
     
  9. baldr

    baldr New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    327
    Enchantner,

    Тов. gorodon прав: в данном случае результат будет оптимален (и единственен заодно). При этом раскладе представлять 6000 как 3*2000 нет смысла, ибо 1000+5000, а остальные кратны. Я привёл неудачный пример для взаимно простых, а потом забыл его поменять на 5+1==3+3 (для взаимно простых, в смысле однозначности расклада).

    Сомнения, наверное, вытекают из ±? В смысле реципиент сдачи может дать сдачи? :derisive:
     
  10. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.615
    Адрес:
    Russia
    baldr
    похожую на вашу задачку про 4 гири знаете ???
    подберите вес 4-х гирь так чтоб ими можно было-бы взвесить любой вес от 1 по 40 кг (с шагом в килограмм)
     
  11. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Rockphorr
    Четырёх гирь хватит только на 15 кг (1, 2, 4, 8). Не?
     
  12. Ravager

    Ravager New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2008
    Сообщения:
    34
    KeSqueer
    Видимо, смысл в том, что гири можно ставить на обе чаши весов - тогда число комбинаций увеличивается.
     
  13. Enchantner

    Enchantner New Member

    Публикаций:
    0
    Регистрация:
    29 июл 2008
    Сообщения:
    23
    gorodon
    а если начальные номиналы другие? И их нельзя просто жадно разложить? Я понимаю, что для моего конкретного примера это работает, но в случае других номиналов... Я потому и хочу именно динамическое решение.
     
  14. asd

    asd New Member

    Публикаций:
    0
    Регистрация:
    12 мар 2005
    Сообщения:
    952
    Адрес:
    Russia
    gorodon
    Выш вариант можно заменить последовательным делением на номиналы монет, начиная со старшего номинала.

    Но при таком подходе не получится оптимально решить задачу со следующими входными данными:
    Номинады монет 1, 125, 300, 400
    Нужно разложить сумму 425
    Правильный ответ 300+125, а не 400 + 1 + ....
     
  15. Ravager

    Ravager New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2008
    Сообщения:
    34
    Enchantner
    Вам нужно решение задачи целочисленного линейного программирования. В интернете есть уйма примеров.
     
  16. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.615
    Адрес:
    Russia
    KeSqueer
    не - 1, 3, 9, 27 - и уже 40
    каждая гиря может быть в 3 состояниях, всего гирь 4
    согласно формуле хартли 81 вариант расположения
    1 из них пустой когда масса 0
    40 пар симметричных вариантов (разница только в том, что левая и правая чаша меняются местами)
    1111(3)=40 все гири собраны на одной чаше
    0001(3)=1
    0010(3)=3
    0100(3)=9
    1000(3)=27
     
  17. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.615
    Адрес:
    Russia
    asd
    видимо вы насщупали область контрпримеров - когда стратегия брать по максимуму не оптимальна
     
  18. gorodon

    gorodon New Member

    Публикаций:
    0
    Регистрация:
    19 окт 2009
    Сообщения:
    301
    asd
    Да, вы правы. Но такая ситуация возникает для тех базисов, где для элемнтов базиса не выполняется условие

    B[n-2]+B[n-1]<=B[n] (1)

    Если же условие (1) выполняется, как в случае, приведенным ТС ({1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000}),
    то алгоритм из #8 работает.... Хотя для общего случая нужны еще доп-е условия (типа B[n]>=2*B[n-1] - ?)...
    Если же условие (1) нарушается, как в вашем примере (B[1]+B[2]>B[3]), то нужен другой алгос...
     
  19. Enchantner

    Enchantner New Member

    Публикаций:
    0
    Регистрация:
    29 июл 2008
    Сообщения:
    23
    Товарищи, мы сейчас вообще говорим о двух разных подходах. То, что предложил gorodon - это решение задачи жадным алгоритмом, работающее только для частных случаев начальных наборов номиналов. Я же хочу найти динамическое решение, которое выдает линейную асимптотику на любом наборе начальных номиналов.
     
  20. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Enchantner
    Фактически, Вам нужно решить линейное уравнение с N неизвестными, причем корни должны быть натуральными. Простейшее решение, как кажется, перебрать все варианты корней, т.е. создать цикл с вложенностью, равной числу номиналов монет.