Форум программистов, компьютерный форум CyberForum.ru

Задача про 2 рюкзака - C++

Восстановить пароль Регистрация
 
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
21.11.2011, 14:26     Задача про 2 рюкзака #1
Дано n предметов a1..an, и дан вес каждого из них. Требуется разделить все предметы на две группы так, чтобы вес каждой из груп был максимально близок.
Если можна на Си.
Заранее благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.11.2011, 14:26     Задача про 2 рюкзака
Посмотрите здесь:

Задача про скобки C++
Задача про матрицу C++
Задача про ракету C++
Задача про монеты C++
Задача про торт C++
C++ Задача про банк
Задача про триугольник C++
Задача про гостей C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
21.11.2011, 17:56     Задача про 2 рюкзака #2
На С не хочу, и оптимальный алгоритм реализовывать лень. Приближением:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
 
int RandomInteger() {
  return rand() % 1000 + 1;
}
 
template <class T>
std::ostream &operator<<(std::ostream &stream, const std::vector<T> &heap) {
  for (typename std::vector<T>::const_iterator i = heap.begin();
    i != heap.end(); ++i)
    stream << *i << " ";
  return stream;
}
 
int main(int argc, char *argv[]) {
  srand(time(NULL));
  size_t stackSize = 10;
  std::vector<int> heap(stackSize);
  std::generate(heap.begin(), heap.end(), RandomInteger);
  std::cout << "Heap:" << std::endl << heap << std::endl;
  std::sort(heap.begin(), heap.end());
  std::cout << "Sorted heap:" << std::endl << heap << std::endl;
  
  std::vector<int> part1, part2;
  int part1Size = 0;
  int part2Size = 0;
  for (std::vector<int>::reverse_iterator i = heap.rbegin(); i != heap.rend(); ++i) {
    if (part1Size > part2Size) {
      part2Size += *i;
      part2.push_back(*i);
    } else {
      part1Size += *i;
      part1.push_back(*i);
    }
  }
  std::cout << "Part one, size = " << part1Size << ":" << std::endl << part1 << std::endl;
  std::cout << "Part two, size = " << part2Size << ":" << std::endl << part2 << std::endl;
}
Yandex
Объявления
21.11.2011, 17:56     Задача про 2 рюкзака
Ответ Создать тему
Опции темы

Текущее время: 17:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru