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

Знаю, что задача "дать сдачу минимальным числом монет заданных номиналов" - классическая, даже школьная задача по динамическому программированию. Но уж очень хочется вникнуть, прорешать такие задачи самому, потому что опыта по алгоритмам катастрофически не хватает.

Сейчас программа выглядит так:

Код (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. И не слишком ли извращенно я задал начальные значения вектору?

 

Enchantner,

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

 

baldr
Если честно, мало что понял. Как надо представить сумму? В чем проблема с взаимной простотой?

 

Enchantner
если монеты образуют степени по одному основанию то формула хартли - если нет то пробуйте применить формулу шенона

 

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.  }

Я на скорую руку написал - можно еще оптимизировать...

 

gorodon
это, насколько я вижу, жадный алгоритм, а мне надо линамическое программирование. Ваш алгоритм далеко не всегда будет выдавать минимальное число монет.

 

Enchantner
вообщем gorodon очень близок к истине - его алгоритм эквивалент переводу числа в другую систему исчисления, пусть даже с неравномерным ростом

 

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.     }

 

Enchantner,

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

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

 

baldr
похожую на вашу задачку про 4 гири знаете ???
подберите вес 4-х гирь так чтоб ими можно было-бы взвесить любой вес от 1 по 40 кг (с шагом в килограмм)

 

Rockphorr
Четырёх гирь хватит только на 15 кг (1, 2, 4, 8). Не?

 

KeSqueer
Видимо, смысл в том, что гири можно ставить на обе чаши весов - тогда число комбинаций увеличивается.

 

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

 

gorodon
Выш вариант можно заменить последовательным делением на номиналы монет, начиная со старшего номинала.

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

 

Enchantner
Вам нужно решение задачи целочисленного линейного программирования. В интернете есть уйма примеров.

 

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

 

asd
видимо вы насщупали область контрпримеров - когда стратегия брать по максимуму не оптимальна

 

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]), то нужен другой алгос...

 

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

 

Enchantner
Фактически, Вам нужно решить линейное уравнение с N неизвестными, причем корни должны быть натуральными. Простейшее решение, как кажется, перебрать все варианты корней, т.е. создать цикл с вложенностью, равной числу номиналов монет.