Category: Dynamic Programming

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 value of the 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 indexes 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 …

Increasing Subsequence with Maximum Sum

Find a subsequence of a given sequence such that subsequence sum is as high as possible and subsequence’s elements are in sorted order, from lowest to highest. This subsequence is not necessarily contiguous, or unique.