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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ генератор псевдослучайных чисел... http://www.cyberforum.ru/cpp-beginners/thread78615.html
Вот програмулька генерирующая псевдослучайные числа создавалась по алгоритму X(n+1)=a*X(n)+c*(mod M) кто может подсказать как выводить те значения которые получаются? я понимаю что с помощью printf(...) только вот не пойму как и куда всунуть... #define RAND_MAX 32767 unsigned long next = 1 ; int rand(void) {
C++ Шифровка и дешифровка текста Помогите, пожалуйста, кто может. Буду очень благодарен. Написать программу шифровки и дешифровки текста по сделующему алгоритму: каждому символу текста поставить в соответствие целое число из заданного диапазона. http://www.cyberforum.ru/cpp-beginners/thread78614.html
C++ Использование подпрограмм
Здравствуйте! Писал прогу и при тестировании наткнулся на то, что неправильно работает т.е я думаю, что неисправность в main, там идет вызов функций и мне надо заставить прогу, чтобы она сразу на все проверяла - совпадение, параллельность, пересечение в одной точке, и выводила в общем положении прямые или нет, а она проверяет только на пересечение в точке и то только 3 прямые, когда я ввожу 20,...
Дана строка. Указать те слова, которые содержат хотя бы одну букву k C++
Решите кто может завтра уже здавать. Я просто представления неимею как их делать, я по С++ не шарю нифига.=(((( 1. Дана строка. Указать те слова, которые содержат хотябы одну букву k. 2. Дана строка, содержащая текст, заканчивающийся точкой. Вывести на экран слова, содержащие три ьуквы. 3. Дана строка. Преобразовать ее, удалив каждый символ * и повторив каждый символ, отличный от *. 4. Дана...
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 pointer to function that returns type "int&". 5. This declaration won't compile.
C++ Рекурсия...Очень нужно решить... Решить задачу вычисления выражения y(x,n) с помощью циклов, затем реализовать рекурсивную ф-цию: http://www.imageup.ru/img89/liv234352.jpg.html Написать нужно на С. Буду очень благодарен за помощь... подробнее

Показать сообщение отдельно
matteo
Сообщений: n/a

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

23.12.2009, 16:54. Просмотров 346. Ответов 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

Помогите ошибку найти и исправить, если можно..
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 18:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru