0/1 Knapsack

Challenge

Implement:

int knapsack(const int *w, const int *v, int n, int cap);

Return the maximum total value of a subset of the n items (weights w, values v) whose total weight is <= cap. Each item is used at most once.

Input format

Weights, values, count, capacity.

Output format

Maximum achievable value.

Constraints

Iterate capacity downward for the 0/1 (once-each) constraint.

Starter code

#include <stddef.h>
/* 0/1 knapsack: max total value of items (weights w, values v, n items) fitting capacity cap. cap>=0, weights/values >=0. */
int knapsack(const int *w,const int *v,int n,int cap){ (void)w;(void)v;(void)n;(void)cap; return 0; }

Common mistakes

Iterating capacity upward turns it into unbounded knapsack (items reused).

Edge cases to handle

cap 0 -> value 0; items heavier than cap are skipped.

Background lessons

• 0/1 Knapsack & subset sum