Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 23.11.2013, 01:51   #1
ds.Dante
Старожил
 
Аватар для ds.Dante
 
Регистрация: 06.08.2009
Сообщений: 2,992
По умолчанию Прошу у вас code review

Всем привет. Я сейчас пишу статью о решении задачи о ранце с помощью кода Грея. Код к статье я бы написал на шарпе, но шарпу очень не хватает функции BitScanForward, которая вызывает процессорную инструкцию find first set, поэтому пришлось писать на C++.

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

Код старался сделать наглядным и лаконичным, поэтому проверку ввода и оптимизацию я не делал.

Код:
#include <iostream>
#include <fstream>
#include <bitset>
#include <intrin.h>
using namespace std;

void main()
{
    int target;            // размер ранца
    int nItems = 0;        // количество предметов
    int weight[31];        // веса предметов
    ifstream inFile("input.txt");
    inFile >> target;
    while(inFile >> weight[nItems])
        nItems++;
    inFile.close();

    const unsigned int nIterations = 1 << nItems; // количество комбинаций, 2^n
    int sum = 0;                                  // текущий вес вещей
    int bestSum = 0;                              // лучший вес (максимальный без перегрузки)
    bitset<31> mask;                              // текущая комбинация выбранных вещей
    bitset<31> bestMask;                          // лучшая комбинация выбранных вещей
    for (unsigned int i = 1; i < nIterations; i++)
    {
        unsigned long position;                   // какой по счёту бит инвертируем
        _BitScanForward(&position, i);
        mask[position] = !mask[position];
        if (mask[position])
            sum += weight[position];
        else
            sum -= weight[position];

        if (sum > target) // перегруз
            continue;
        if (sum > bestSum)
        {
            bestSum = sum;
            bestMask = mask;
        }
    }

    cout << "Best approximation: " << bestSum << endl;
    cout << "Used weights:" << endl;
    for (int i = 0; i < 31; i++)
        if (bestMask[i])
            cout << weight[i] << endl;
    cin.get();
}

Последний раз редактировалось ds.Dante; 23.11.2013 в 02:05.
ds.Dante вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Очень прошу!!!!! Последняя надежда на вас..... Кристинка- Фриланс 0 19.05.2012 20:19
Очень прошу!!!!! Последняя надежда на вас..... Кристинка- Общие вопросы Delphi 1 19.05.2012 19:49
Многоуважаемые программисты, Прошу вас о помощи! Ivanich87 Свободное общение 1 12.01.2009 13:51