[Algorithm] Classic algorithm and greedy algorithm solutions to the knapsack problem, implemented in C language.

On the eve of Christmas, let's talk about some algorithms that have a Christmas feel to them - the knapsack problem algorithms. Here, I have written two methods to solve this problem: the classic algorithm and the greedy algorithm. Since we don't have much time, the given array is already sorted. Sorting is not as important for the classic algorithm because it compares items one by one. The final result of both algorithms may be the same. When debugging, remember to modify the test array I provided. I've been really busy today, so I didn't write the sorting algorithm used by the greedy algorithm. I'll save it for when I talk about sorting algorithms in the future. Merry Christmas, everyone!

Knapsack Problem: You have a knapsack with a capacity of PSIZE and N items. The goal is to put these items into the knapsack, following certain requirements (such as sorting by size), and maximize the number or total value of the items.

Now that we've discussed the problem, here are the algorithms implemented in C. I will also write backtracking and dynamic programming algorithms when I have time. But for now, please look forward to them.

/* Classic and Greedy Algorithms for the Knapsack Problem
 * code cg
 * 2008 12 24
 * Debugging environment: TC, DevC++
 */
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 5 /* Define the number of items to be placed */
#define PSIZE 150 /* Define the size of the knapsack */

long item[N] = {15, 40, 50, 60, 90}; /* Initialize the item array, which needs to be sorted for the greedy algorithm */
int freespace[N] = {0};

int classic() { /* Classic algorithm */
    long size = PSIZE;
    long used = 0;
    int i;
    for(i = N - 1 ; i >= 0 ; i--){
        if((size - used) >= item[i]){ /* Can it fit in the size? */
            used += item[i]; /* Put it in the knapsack and update the used size */
            freespace[i] = 1;
        }
        else { /* Size is too large */
            freespace[i] = 0;
        }
    } /* for */
    return 1;
}

int greedy(){ /* Greedy algorithm */
    int i;
    long size = PSIZE;
    long used = 0;
    for(i = N - 1 ; i >= 0 ; i--){ /* Put larger items first, then consider smaller items */
        if((used + item[i]) <= size){ /* Can the current item be put in? */
            freespace[i] = 1; /* 1 indicates putting it in */
            used += item[i]; /* Reduce the remaining capacity of the knapsack */
        }
        else{
            freespace[i] = 0;
        }
    } /* for */
    if(size == used) /* Return */
        return 1;
    else
        return 0;
}

void main(){
    int i; /* Counter */
    for(i = 0 ; i < N ; i++){
        if(i % 5 == 0 )
            printf("\n");
        printf("%10ld" , item[i]); /* First, input the original data */
    } /* for */
    printf("\nClassic\n");
    if(classic()==1){ /* Classic algorithm */
        printf("Result:\n");
        for(i=0;i<N;i++){
            printf("%10d",freespace[i]);
        }
    }
    printf("\nGreedy\n");
    if(greedy()==1){ /* Greedy algorithm */
        printf("Result:\n");
        for(i=0;i<N;i++){
            printf("%10d",freespace[i]);
        }
    }
}