Category: Dynamic Programming

Rod Cutting Problem

Given a rod of length n and list of prices of rod of length i where 1 < = i

Minimum Sum Partition problem

Given a set of positive integers S, partition the set S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized.

Subset Sum Problem

Given a set of positive integers and an integer s, is there any non-empty subset whose sum to s.

Maximize the Value of an Expression

Given an array A, maximize value of the expression (A[s] – A[r] + A[q] – A[p]) where p, q, r and s are indices of the input array and s > r > q > p.

0-1 Knapsack problem

In 0-1 Knapsack problem, we are given a set of items, each with a weight and a value and we need to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as …