Загрузка оборудования(вариант "Задачи о ранце")

[matteo]

Формулировка:
Дан список деталей(время изготовления, прибыль за деталь), кол-во деталей и ограничение по времени. Нужно вывести максимальную прибыль и кол-во деталей каждого типа для достижения этой максимальной прибыли.
Пример:
инпут файл(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

Помогите ошибку найти и исправить, если можно..

[07zaharov]

Уважаемый коллега,
Выложите шаблон в Excel, чтоб посмотреть и найти решение)