1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
1

Задача про 2 рюкзака

21.11.2011, 14:26. Показов 1798. Ответов 1
Метки нет (Все метки)

Дано n предметов a1..an, и дан вес каждого из них. Требуется разделить все предметы на две группы так, чтобы вес каждой из груп был максимально близок.
Если можна на Си.
Заранее благодарен.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.11.2011, 14:26
Ответы с готовыми решениями:

Задача о рюкзаке: упаковать рюкзак так, чтобы общая ценность предметов была наибольшей и вес не превышал объем рюкзака
«ЗАДАЧА О РЮКЗАКЕ» Путешественник собрался в поход. Перед ним 5 предметов, для каждого известна...

Задача про взлом кода из книги Эрика Фримена про основы javascript в конце 5 главы.
читаю книгу Эрика Фримена про основы javascript.В конце 5 главы есть задачка про взлом кода.Никак...

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он...

Наполнение рюкзака
Дан рюкзак объёма W и n предметов с объемом w и стоимостью i ci Напишите программу находящую самое...

1
3977 / 2029 / 730
Регистрация: 29.11.2010
Сообщений: 4,356
21.11.2011, 17:56 2
Лучший ответ Сообщение было отмечено Shab13 как решение

Решение

На С не хочу, и оптимальный алгоритм реализовывать лень. Приближением:
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;
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.11.2011, 17:56
Помогаю со студенческими работами здесь

Задача про IP
Простите что не совсем в тему , но у меня ответ 97.15.81.53/15 , но говорят это неправильно ...

Как работает алгоритм ПП рюкзака?
Здравствуйте, вот код полного перебора рюкзака. Все понимаю, кроме главного цикла, где всё...

Шифрование методом укладки рюкзака
Ребят прошу помочь тех кто знает как на с++ шифровать сообщения и дешифровывать методом укладки...

Задача про журавликов
Катя, Петя и Вася собирали журавликов. У Кати их было в два раза больше чем у Пети и Васи вместе....

Задача про робота
Посланный на колонизацию планеты Тау-Кита робот опустился в точку с координатами (0;0). Робот...

Задача про камни
Привет! Не могу понять с чего начинать копать..., помогите пожалуйста Дано: N камней различного...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru