Форум программистов, компьютерный форум, киберфорум
Наши страницы

knapsack(подсчет предметов) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ генератор псевдослучайных чисел... http://www.cyberforum.ru/cpp-beginners/thread78615.html
Вот програмулька генерирующая псевдослучайные числа создавалась по алгоритму X(n+1)=a*X(n)+c*(mod M) кто может подсказать как выводить те значения которые получаются? я понимаю что с помощью...
C++ Шифровка и дешифровка текста Помогите, пожалуйста, кто может. Буду очень благодарен. Написать программу шифровки и дешифровки текста по сделующему алгоритму: каждому символу текста поставить в соответствие целое число из... http://www.cyberforum.ru/cpp-beginners/thread78614.html
C++ Использование подпрограмм
Здравствуйте! Писал прогу и при тестировании наткнулся на то, что неправильно работает т.е я думаю, что неисправность в main, там идет вызов функций и мне надо заставить прогу, чтобы она сразу на все...
Дана строка. Указать те слова, которые содержат хотя бы одну букву k C++
Решите кто может завтра уже здавать. Я просто представления неимею как их делать, я по С++ не шарю нифига.=(((( 1. Дана строка. Указать те слова, которые содержат хотябы одну букву k. 2. Дана...
C++ int * & func(); http://www.cyberforum.ru/cpp-beginners/thread78574.html
int * & func(); What is func? 1. A function that returns pointer to type "int&". 2. A function that returns reference to type "int*". 3. A reference to function that returns type "int*". 4. A...
C++ Как перейти от char[100] к *char? Подскажите, как переделать 6 строчку? char str1; cin.getline(str1, 100); // Some text char *str2; // strcpy(*str2, str1); подробнее

Показать сообщение отдельно
matteo
0 / 0 / 0
Регистрация: 02.07.2013
Сообщений: 28

knapsack(подсчет предметов) - C++

23.12.2009, 16:54. Просмотров 381. Ответов 0
Метки (Все метки)

Получил задание - решить враиант задачи о ранце(knapsack)..
Формулировка задачи:
Дан список деталей(время изготовления, прибыль за деталь), кол-во деталей и ограничение по времени. Нужно вывести максимальную прибыль и кол-во деталей каждого типа для достижения этой максимальной прибыли.
Пример:
инпут файл(2 детали, тайм-лимит 6, у первой детали время 1, прибыль 4, у второй время 4, прибыль 5):
2 5
1 1
4 5
Результат:
кол-во деталий 1го типа 1
кол-во деталей второго типа 1
Макс Прибыль 6

Посчитать макс прибыль у меня получилось, а вод список деталей с количеством каждой - проблема. Мой код:

Код
#include <string.h>
#include <stdio.h>
#include <errno.h>

int max(int a, int b){
    if (a>b)
        return a;
    return b;
}
int solver(int *time, int *profit, int *quantity, int b, int n){
    int *temp = new int [b+1]; //рабочий массив
    int optimal_profit; // прибыль от выбранной детали
    for (int j=0;j<n;j++)// подготовка подсчета
        quantity[j]=0; // кол-ва деталей каждого типа
    temp[0] = 0;// начало рабочего массива - 0
    for (int k = 1; k <= b; k++)// k приниает заначения от 1 до
    {                           // ограничения по времени
        temp[k] =0;
        for (int i = 0; i < n; i++)// пересичляем все типы деталей
        {
            if (time[i] <= k) // выбираем так, что бы время
                              // не привысило ограничение
            {
                temp[k] = max(temp[k], temp[k - time[i]] + profit[i]);//ищем
                // максимальную прибыль
                optimal_profit=profit[i]; // получаем номер
                // Использованной детали
            }
        }
        for (int j=0;j<n;j++)
            if (optimal_profit == profit[j])
                quantity[j]++;

    }
    return temp[b];
}
int main() {
    int order_quantity; /*количество заказов */
    int time_limit;     /*ресурс времени станка */

    int total_profit=0; /* суммарная прибыль */
    int *time; // массив времени необх для каждой детали
    int *profit; // массив прибыли каждой детали
    int *quantity; // массив кол-ва деталей каждого типа
 /**
     *Открытие файлов с проверкой..
     */
    if(!(freopen("input.txt","r",stdin))) {
        fprintf(stderr, "%s\n", strerror(errno));
        return 1;
    }

      scanf("%d",&order_quantity);
      scanf("%d",&time_limit);
    /*Создаем массив заказов и заполняем его */
     time = new int [order_quantity];
     profit = new int [order_quantity];
     quantity = new int [ order_quantity];
     for (int i=0;i<order_quantity;i++){
        scanf("%d",&time[i]);
        scanf("%d",&profit[i]);
        quantity[i]=0;
    }

     total_profit = solver(time, profit, quantity, time_limit, order_quantity);

     for (int i=0;i<order_quantity;i++)
        printf("\n Order number: %d, Quantity of details: %d",i+1, quantity[i]);

    /* Вывод суммарной прибыли */
    printf("\n Total profit: %d\n", total_profit);

    /* oчистка памяти */
    delete time;
    delete profit;
    return 0;
}
при вводе инпут файла из примера( 2 5 1 1 4 5)
Выдает:

Order number: 1, Quantity of details: 3
Order number: 2, Quantity of details: 2
Total profit: 6

Помогите ошибку найти и исправить, если можно..
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru