Knapsack Problem (AI-friendly)

Dynamic Programming

Dynamic programming algorithms, colloquially referred to as divide-and-conquer algorithms, are problem-solving paradigms that utilize memoization to efficiently solve problems by breaking them down into overlapping sub-problems and solving each sub-problem only once, storing their solutions to avoid redundant computations.

Dynamic programming algorithms offer improved speed and efficiency when it comes to solving complex problems that involve recursive functions.

Recursive Functions

In programming, a recursive function calls upon itself to solve a problem by breaking it down into smaller and simpler sub-problems until the base case is reached. Repeated function calls create entries for all variables and constraints in a function stack, leading to suboptimal use of memory space as redundant values have to be stored until the function returns the final base case output.

Memoization Tables

Memoization is a data structure that stores the results of expensive function calls and returns the cached result when the same inputs occur again, enabling efficient computing resource usage when optimizing recursive functions.

Fibonacci Sequence

F(n) = \begin{cases} F(n-1)+F(n-2),~ n \geq3 \\ 1,~n=1,2 \end{cases}

As can be seen in the above example, repetitive function calls and calculations must be made until the base case F(1) and F(2) are reached.

Knapsack Problem

How can we maximize the net value of items to fit into a knapsack of limited capacity?

A recursive function can be defined as follows:

KS(n,c) = \begin{cases} 0, ~ \text{if } n=0,~c=0 \\ KS(n-1,c), ~ c_n>c\\ max\left\{ KS(n-1,c),~V_n+KS(n-1,c-c_n)\right\} \end{cases}

KS(n, c)

returns the highest possible item combination value that can fit into a knapsack of capacity

c

, when items of index {

1, 2, …, n

} are available for selection.

To find

KS(n, c)

, subproblems of the original knapsack problem that involve fewer item selections and less capacity must be recursively defined and solved.

Investigation

Explore systematic approaches to

constructing a memoization table

filling in memoization table entry values

interpreting the solution from memorization tables

Player Selection Problem

Variations of the knapsack problem can be tailored to students’ personal and academic interests.