VPF::[с/с++]Составление числа из заданного набора

zayats36

Дата 12.12.2011, 19:07 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 27.11.2011

Репутация: нет
Всего: нет

Задача для решения на с/c++:

Имеются 10 гирь весом 100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000 и 3000 г. Сколькими способами гирями этого набора можно составить вес в v граммов (и кратно 100)? На экран вывести количество способов.
(Например, число 500 можно составить двумя способами: 1 - 200+300, 2 - 500).

BestCoder1

Дата 13.12.2011, 09:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 38
Регистрация: 25.11.2011

Репутация: -1
Всего: -1

Могу сделать
icq: 588002847
email: [email protected]
skype: rfhfcerf

t_gran

Дата 13.12.2011, 17:55 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Хотел сначала реализовать на C, а потом не стал заморачиваться и перешёл на контейнеры С++ (так проще, нежели свои АТД воять)

Код


#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void Print(stack<unsigned> st)
{
   while (!st.empty())
   {
      cout << st.top() << " ";
      st.pop();
   }
   cout << endl;
}

void ChooseCombination(vector<unsigned>& list, int weight, unsigned current = 0)
{
   static stack<unsigned> elem;

   while ((current < list.size()) && ((signed)list[current] <= weight))
   {
      elem.push(list[current]);
      
      if ((signed)elem.top() == weight)
      {
         Print(elem);
      }
      else
      {
         ChooseCombination(list, weight-elem.top(), current+1);
      }
      
      elem.pop();
      current++;
   }
}

int main()
{
   const unsigned CList[] = {100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000, 3000};

   vector<unsigned> list(CList, CList + sizeof(CList)/sizeof(*CList));
   
   ChooseCombination(list, 500);

   return 0;
}

Выполнение на вес 3300 можно посмотреть тут

Исходник с демонстрационным бинарником ниже

Присоединённый файл ( Кол-во скачиваний: 5 )

archive.7z 69,91 Kb

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »