Мне нужно решить проблему рюкзака рекурсивно, памятью и динамическим программированием. В настоящее время я придерживаюсь метода динамического программирования.проблема с решением проблемы с рюкзаком с помощью динамического программирования в C
Я адаптировал код из того, что нашел в другом месте в Интернете. В настоящее время вывод неправильный.
Проблема связана с прибылью и массой. Каждый элемент имеет связанную с прибылью и массой, имеется MAX_N (umber) доступных предметов и MAX_CAPACITY для массы. Цель состоит в том, чтобы иметь как можно больше «прибыли» в рюкзаке.
Ниже приведен пример, приведенный в упражнении:
Пример: С учетом ранец емкости 5, и элементы с массой [] = {2, 4, 3, 2} и прибыли на прибыль [] = {45, 40, 25, 15}, лучшей комбинацией будет пункт 0 (с массой 2 и прибыль 45) и пункт 2 (с массой 3 и с прибылью 25) на общую прибыль 70. Никакая другая комбинация с массой 5 или менее имеет большую прибыль.
Вот полный код:
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 10
#define MAX_CAPACITY 165
int m[MAX_N][MAX_CAPACITY];
int max(int x, int y) {
return x^((x^y) & -(x < y));
}
int min(int x, int y) {
return y^((x^y) & -(x < y));
}
int knapsackRecursive(int capacity, int mass[], int profit[], int n) {
if (n < 0)
return 0;
if (mass[n] > capacity)
return knapsackRecursive(capacity, mass, profit, n-1);
else
return max(knapsackRecursive(capacity, mass, profit, n-1), knapsackRecursive(capacity - mass[n], mass, profit, n-1) + profit[n]);
}
int knapsackMemoized(int capacity, int mass[], int profit[], int n) {
}
int knapsackDynamic(int capacity, int mass[], int profit[], int n) {
int i;
int j;
for (i = 0; i <= n; i++) {
for (j = 0; j <= capacity; j++) {
if (i == 0 || j == 0)
m[i][j] = 0;
else if (mass[i-1] <= j)
m[i][j] = max(profit[i-1] + m[i-1][j-mass[i-1]], m[i-1][j]);
else
m[i][j] = m[i-1][j];
}
}
return m[n][capacity];
}
void test() {
// test values
//int M1[MAX_N] = {2, 4, 3, 2};
//int P1[MAX_N] = {45, 40, 25, 10};
int M1[MAX_N] = {6, 3, 2, 4};
int P1[MAX_N] = {50, 60, 40, 20};
int M2[MAX_N] = {23, 31, 29, 44, 53, 38, 63, 85, 89, 82};
int P2[MAX_N] = {92, 57, 49, 68, 60, 43, 67, 84, 87, 72};
// a)
printf("Recursion: %d\n",knapsackRecursive(MAX_CAPACITY, M1, P1, MAX_N));
printf("Recursion: %d\n",knapsackRecursive(MAX_CAPACITY, M2, P2, MAX_N));
printf("\n");
// b)
printf("Memoization: %d\n",knapsackMemoized(MAX_CAPACITY, M1, P1, MAX_N));
printf("Memoization: %d\n",knapsackMemoized(MAX_CAPACITY, M2, P2, MAX_N));
printf("\n");
// c)
printf("Dynamic Programming: %d\n",knapsackDynamic(MAX_CAPACITY, M1, P1, MAX_N));
printf("Dynamic Programming: %d\n",knapsackDynamic(MAX_CAPACITY, M2, P2, MAX_N));
}
int main() {
test();
}
Это выход я в настоящее время получить. Рекурсивный метод должен обеспечивать правильный результат, но динамическое программирование в настоящее время не выводит то же самое. Запоминание еще не завершено, поэтому оно также не выводится правильно.
Recursion: 170
Recursion: 309
Memoization: 2686680
Memoization: 2686600
Dynamic Programming: 0
Dynamic Programming: 270
Process returned 25 (0x19) execution time : 0.269 s
Press any key to continue.