1
我需要解決遞歸，memoized和動態編程的揹包問題。目前我被困在動態編程方法中。通過C中的動態編程解決揹包問題的麻煩
我改編了我在互聯網上其他地方找到的代碼。目前輸出不正確。
問題涉及利潤和質量。每個項目都有一個利潤和質量關聯，有一個MAX_N（棕色）項目可用，一個質量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();
}
這是輸出我目前得到的。遞歸方法應該提供正確的結果，但動態編程當前不會輸出相同的結果。 Memoization還沒有完成，因此它也沒有正確輸出。
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.