Today, I will discuss the last type of solution to the knapsack problem, which is the recursive solution. This solution is one of the basic solutions taught in algorithm textbooks. If you have a book about this type of algorithm, you can usually find the algorithm you are looking for. For a specific explanation of the knapsack problem, you can refer to my previous articles. You can find them in the related links below. I recently published articles about the basic solution, dynamic programming solution, and backtracking solution to the knapsack problem. You can directly refer to the links on my page. If you have any specific questions or don't understand something, please feel free to leave a comment.
Now, let's talk about the recursive algorithm. The algorithm I provide uses the effective weight and maximum available value as recursive parameters to test the weight and value of each item one by one until the best solution is found. Please note that the condition I set here is that as long as the item can fit in the knapsack, it is considered valid. This is not a greedy algorithm, so please pay attention to the difference.
I believe you can understand the other parts of the code by reading the comments. If you still have any unclear parts, please feel free to leave a comment, and I will try my best to answer. I am currently busy with exams, so I may be quite busy recently. Thank you for your understanding.
Here is the code: Debugging environment: GCC, TC
/*
- Recursive Solution to the Knapsack Problem
- code CG
- 2008 12 30
*/
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
#define N 5 /* Control the number of input elements /
#define MAX 100 / Maximum weight the knapsack can hold */
int result;
int select[N], selectW[N];
struct{
int weight;
int price;
}items[N]; /* Define the item structure */
/*
- knapsacks() - Recursive knapsack algorithm
- Parameters: int i - index of the item to be placed
int w - current weight of the knapsack
int p - maximum available price
/
void knapsacks(int i, int w, int p){
int k;
if ((w + items[i].weight) <= MAX){ / Check if the weight of item i can fit in the knapsack /
selectW[i] = 1; / Temporarily place the item in the knapsack /
if (i < N - 1){ / i < N-1? /
knapsacks(i + 1, w + items[i].weight, p);
}
else{
for (k = 0; k < N ; k++){
select[k] = selectW[k]; / Copy selectW to select /
}
result = p;
}
}
if (p - items[i].price > result){ / If item i is not placed in the knapsack, revert the changes /
selectW[i] = 0;
if (i < N - 1){
knapsacks(i + 1, w, p - items[i].price);
}
else{
for(k = 0; k < N; k++){ / Copy selectW to select */
select[k] = selectW[k];
}
result = p - items[i].price;
}
}
}
int main(){
int i;
int w = 0, v = 0;
int sumPrice = 0; /* Counter for input /
int maxWeight = MAX;
printf("input W and V: w, v\n");
for (i = 0; i < N ; i++){
scanf("%d, %d", &w, &v);
items[i].weight = w;
items[i].price = v;
printf("W = %d, P = %d\n", items[i].weight, items[i].price);
selectW[i] = 0; / Clear the record array /
select[i] = 0;
sumPrice += v; / Record the total price /
}
printf("Max Weight: %d\n", maxWeight);
result = 0;
printf("sumPrice: %d\n", sumPrice);
knapsacks(0, 0, sumPrice); / Start the knapsack operation */
printf("| ID | WT | PR |\n");
for (i = 0; i < N; i++){
if (select[i]){
printf("|%-4d|%-4d|%-4d|\n", i+1, items[i].weight, items[i].price);
}
}
printf("Result: %d\n", result);
system("PAUSE");
return 0;
}
Translation: