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

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

Восстановить пароль Регистрация
 
matteo
Сообщений: n/a
23.12.2009, 16:54     knapsack(подсчет предметов) #1
Получил задание - решить враиант задачи о ранце(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

Помогите ошибку найти и исправить, если можно..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2009, 16:54     knapsack(подсчет предметов)
Посмотрите здесь:

C++ известна масса каждого из 12 предметов определить общую массу всего набора предметов ?
C++ Оперделить общую массу предметов (через цикл)
В массиве хранится сведения о стоимости 12 различных предметов. определить общую стоимость всех предметов? C++
5.40 Известна масса каждого из 12 предметов. Определить общую массу все¬го набора предметов C++
Сделать так, что бы в общем балле отображался сумма, складываемых 4 предметов и деленный на тот же количество предметов C++
Определить максимальную плотность материала по данным о массе и объеме 20-ти предметов C++
Вычислить количество способов группировки K предметов из N при больших N C++
C++ Сравнение названий предметов

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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