[Algorithm] Recursive solution to the simple knapsack problem, implemented in the C programming language.

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
    #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 */
return 1;

Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.