Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
d3vn
2 / 2 / 5
Регистрация: 18.11.2013
Сообщений: 118
1

Задача про рюкзак

28.04.2015, 21:35. Просмотров 811. Ответов 2
Метки нет (Все метки)

Всем привет!
Есть программа, которая решает задачу про рюкзак.
Когда у меня количество "предметов" 5 или 10, то все работает хорошо. Как только количество предметов становится 100 и более, то вылетает либо стек оверфлоу, либо программа циклится и ниче не выводит. Помогите отладить, пожалуйста.
Исходные файлы приложил. Спасибо.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int knapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    int K[100][100];
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
    return K[n][W];
}
 
int main(int argc, char* argv[])
{
    argv[1] = "input_100.txt";
    int i, j, n, W, startPosition = 0, nextPosition;
    int cost = 0;
    int weight = 1;
    int B[100];
    int C[100];
    int** A = ReadArrayFromFile(&n, &W, argv[1]);
    for (i = 0; i < n; i++)
        B[i] = A[i][weight];
    for (i = 0; i < n; i++)
        C[i] = A[i][cost];
    cout << W << " " << n << endl;
    cout << knapSack(W, B, C, n);
    system("pause");
    return 0;
}
0
Вложения
Тип файла: txt input_100.txt (987 байт, 16 просмотров)
Тип файла: txt input_500.txt (6.2 Кб, 12 просмотров)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2015, 21:35
Ответы с готовыми решениями:

Задача про рюкзак
Из заданных N предметов выбрать такие, чтобы суммарный вес был менее 30 кг, а...

Задача про рюкзак - ускорить работу программы
Вообщем есть алгоритм, который работает правильно за O(N*W), поэтому при...

Задача о камнях (почти рюкзак) модификация)
из камней весом p1, p2 ... pn набрать вес W если это возможно вывести yes, если...

Задача про зайца
В небольшой посадке живет заяц. Выскочив из норы и бегая по снегу, он оставил...

Задача про самолет
Здравствуйте.вопрос,вернее просьба разрбраться в своем же коде.писал честно...

2
Людвиг Бодмер
356 / 355 / 211
Регистрация: 29.03.2013
Сообщений: 866
Завершенные тесты: 4
29.04.2015, 11:32 2
d3vn, так может увеличить размерности массивов?
0
d3vn
2 / 2 / 5
Регистрация: 18.11.2013
Сообщений: 118
29.04.2015, 16:58  [ТС] 3
Людвиг Бодмер, пробовал, не помогает
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2015, 16:58

Задача про банку
Вася живет в стране Осьляндии, где, как всем известно, люди хранят деньги в...

Задача про графы
помогите если не сложно Тексты нужно переписывать в тело сообщения!

Задача про дроби
Сделал вроде всё правильно, но задача не работает и выдаёт ошибку на...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru