Advanced Exercism • c

Knapsack

Challenge Overview

Given a knapsack that can only carry a certain weight, determine which items to put in the knapsack in order to maximize their combined value.

Visit the knapsack exercise on Exercism to read the full instructions and download the exercise files.

Community Solutions

View Community Solutions

The following are the top 3 community solutions by stars:

Solution 1 by @stackcats (⭐ 0) — View on Exercism
Solution 2 by @Jadilathish (⭐ 0) — View on Exercism
Solution 3 by @b3dwyr (⭐ 0) — View on Exercism

Source: Exercism c/knapsack

💡 View Solution

#include "knapsack.h"
#include <stdlib.h>
#include <string.h>

#define max(x, y) (((x) > (y)) ? (x) : (y))

unsigned int maximum_value(unsigned int maximum_weight, const item_t* items, size_t item_count) {
    unsigned int* dp = malloc(sizeof(unsigned int) * (maximum_weight+1));
    memset(dp, 0, sizeof(unsigned int) * (maximum_weight+1));
    for (size_t i = 0; i < item_count; i++) {