Задача о ранце

[Natysya]

Я добавлю библиотеку iostream.h и всё будет работать.

[Д_М]

Сообщение от Natysya

Я добавлю библиотеку iostream.h и всё будет работать.

В C++ будет. В C - нет. И включать по-хорошему надо <iostream> без .h

Насчет числа предметов в ранце. Решение неоднозначно.

Пример - есть 2 предмета
предмет_1 : вес=1 цена=1
предмет_2 : вес=2 цена=2

Макс. вес=2

Можно взять 2 * предмет_1 или 1 предмет_2.

Какое число нужно? Минимальное, максимальное, любое?

[Natysya]

нужны все возможные варианты!

[Serge_Bliznykov]

Насчет числа предметов в ранце. Решение неоднозначно.

точно. может быть несколько вариантов.
в приведённом Вами случае оба решения подходят как полностью эквивалентные!

и что? это что-то меняет?

[Д_М]

и что? это что-то меняет?

Меняет Надо выводить число предметов в ранце.

[Serge_Bliznykov]

Надо выводить число предметов в ранце.

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


p.s. когда я пишу в данной теме, у меня чёткое ощущение, что я оффтоплю...

[Obey-Kun]

Сообщение от Natysya

Я добавлю библиотеку iostream.h и всё будет работать.

В C такой библиотеки нет.

[Д_М]

Сообщение от Natysya

нужны все возможные варианты!

Точно все варианты нужны? Отслеживать все альтернативы может оказаться накладно

[Д_М]

int main()
{
...
  w=new int [n];
  v=new int [n];
  mas=new int [W+1];
  int* cnt = new int [W+1];
...
  mas[0] = 0;
  cnt[0] = 0;
  for (int j = 1;j <= W; j++){
    mas[j] = mas[j-1];
    cnt[j] = cnt[j-1];
    for(i = 0; i < n; i++){
      if(w[i] <= j){
        int probe = mas[j - w[i]] + v[i];
        if(mas[j] < probe) {
            mas[j] = probe;
            cnt[j] = cnt[j-w[i]] + 1;
        }
      }
    }
  }
  cout<<"Max price = "<<mas[W] <<  " objects count = " << cnt[W] << endl;
  return 0;
}

Как-то так. Выводит только один из возможных вариантов количества предметов.
Для вывода всех вариантов надо сделать cnt массивом множеств и добавить обработку случая mas[j] == probe