Today, let's talk about a simple algorithm, the simplest knapsack 0 algorithm, which uses a recursive method. I believe that after reading the code, friends will find it familiar. However, the purpose of providing these codes by CG is to provide a complete knapsack algorithm to everyone. The code is very simple, and I believe that experts will understand it at a glance. This knapsack algorithm only considers the weight of the items and does not consider their value. It is a code that beginners of recursive algorithms must see, and experts can use it as a review. Because CG has exams recently, I have to take 6 exams in one go, so the blog updates will not be as fast. Please understand. However, I will still maintain the speed of providing at least one article per day. I hope everyone can support it. Thank you. Tomorrow's algorithm blog post will be a preview of the "Banker's Algorithm". Today, I reviewed the operating system and reinstalled it at night, wasting two hours. After debugging the code tomorrow, I will provide it. I hope everyone will continue to follow.
/* Recursive Solution to the Simple Knapsack Problem
- code CG 2009-01-04
/
#include"stdio.h"
#define N 6 / Number of items /
#define S 15 / Size of the knapsack */
int W[N+1]={0,1,2,3,4,5,6};/* Test data, weights of each item, W[0] is not used */
/* knapsack() function
Parameters: int s - remaining weight
int n - remaining number of items
Returns: int - whether the knapsack allocation is successful
/
int knapsack(int s, int n){
if(s == 0)/ Allocation finished, successful /
return 1;
if(s < 0 || (s > 0 && n < 1))/ No available space or all items allocated /
return 0;
if(knapsack(s - W[n], n - 1)){/ Recursive /
printf("%-4d",W[n]); / Output /
return 1;
}
return knapsack(s, n - 1);
}
int main()
{
if(knapsack(S, N))/ Recursive call */
printf("OK!\n");
else
printf("Failed!");
return 1;
}/main/