Today I will talk about the last solution to the knapsack problem, the recursive solution. This solution is also one of the basic solutions taught in algorithm textbooks. If you have a book about this type of algorithm, you can generally find the algorithm you want. For the specific details of the knapsack problem, you can refer to my previous articles, which can be found directly in the related links below. I recently published basic solutions, dynamic programming solutions, and backtracking solutions for the knapsack problem. You can refer to my page links directly. If you have any specific questions or don't understand anything, please feel free to leave a comment.
Okay, 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 knapsack can hold, it is considered a valid solution, not a greedy algorithm. Please pay attention to the difference.
I believe you can understand the other questions by reading the code comments. If you still have any unclear parts, please feel free to leave a comment. I have been busy with exams recently, so I may be busy, please understand.
The code is as follows: 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 structure of the items */
/*
* knapsacks() - recursive algorithm for the knapsack problem
* Parameters: int i - the cursor position of the item to be placed
int w - the weight of the knapsack used
int p - the maximum price that can be used
*/
void knapsacks(int i, int w, int p){/* Recursive algorithm for the knapsack problem */
int k;
if ((w + items[i].weight) < = MAX){ /* Does putting item I's weight into the knapsack satisfy the condition? */
selectW[i] = 1; /* If the weight is satisfied, temporarily put it into 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];/* selectW -> select */
}/* for */
result = p;
}/* else */
}/* if */
if (p - items[i].price > result){/* If not putting item I into the knapsack restores the condition */
selectW[i] = 0;
if (i < N - 1){
knapsacks(i + 1, w ,p - items[i].price);
}
else{
for(k = 0; k < N; k++){/* selectW -> select */
select[k] = selectW[k];
}
result = p - items[i].price;
}/* else */
}/* if */
}/* knapsacks */
int main(){
int i;
int w = 0,v = 0;
int sumPrice = 0; /* Input counter */
int maxWeight = MAX;
printf("input W and V ,vn");
for (i = 0; i < N ; i++){
scanf("%d,%d",&w,&v);
items[i].weight = w;
items[i].price = v;
printf("W = %d,P = %dn",items[i].weight, items[i].price);
selectW[i] = 0; /* Clear the record array */
select[i] = 0;
sumPrice += v; /* Record the total price data */
}/* for */
printf("Max Weight:%dn", maxWeight);
result = 0;
printf("sumPrice:%dn", 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);
}
}/* for */
printf("Result:%dn", result);
system("PAUSE");
return 0;
}