Contents

1. 1. Dynamic Programming
2. 2. Backpack Problems
   1. 2.1. 0-1 Backpack Problem
   2. 2.2. Complete Backpack Problem
   3. 2.3. Backpack Problems in Leetcode
      1. 2.3.1. Partition Equal Subset Sum
      2. 2.3.2. Coin Change

Dynamic Programming

“Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map,etc).
Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.
So the next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time.”

from Top 50 Dynamic Programming Practice Problems

Backpack Problems

Backpack problems are typical DP problems, in most backpack problems, we have many items to be taken or not, which lead many “states” when proceeding the items, so we will store these “state” when we check the items one by one.

0-1 Backpack Problem

Give a V as the Volume of backpack, Ci and Wi as the cost and weight of itme i, find the soluion to get more weight in backpack and make sure the total cost < V.

To solve this problem, first we need an Array Ai with length V+1, Ai represents the curent best weight when the volume is temporary set to i in the one of proceedings of items. We will update this Array when proceeding the items and make sure “state” of the proceeded items is stored in this Array.

How to determind the Ai in Proceeding of Ci?
for i = V -> Ci:
Ai = max{ A[i-Ci] + Wi > A[i] }

Example: items(Ci:Wi)=[5:12, 4;3, 7:10, 2:3, 6:6], V=15

Proceedings:
[0 1 2 3 4   5   6   7   8   9 10 11 12 13 14 15]
[0 0 0 0 0 12 12 12 12 12 12 12 12 12 12 12]
[0 0 0 0 3 12 12 12 12 15 15 15 15 15 15 15]
[0 0 0 0 3 12 12 12 12 15 15 15 22 22 22 22]
[0 0 3 3 3 12 12 15 15 15 15 18 22 22 25 25]
[0 0 3 3 3 12 12 15 15 15 15 18 22 22 25 25]

Complete Backpack Problem

Give a V as the Volume of backpack, Ci and Wi as the cost and weight of itme i. each item can be used multiple times. find the soluion to get more weight in backpack and make sure the total cost < V.

Similiar to 0-1 Backpack problem, the different is the way to determind the Ai in Proceeding of Ci:

for i = Ci -> V: (means that each item can be used multiple times)
Ai = max{ A[i-Ci] + Wi > A[i] }

Example: items(Ci:Wi)=[ 4;3, 7:10, 5:12, 2:3, 6:6], V=14

Proceedings:
[0 1 2 3 4   5   6   7   8   9 10 11 12 13 14]
[0 0 0 0 3   3   3   3   6   6   6   6   9   9   9]
[0 0 0 0 3   3   3 10 10 10 10 13 13 13 20]
[0 0 0 0 3 12 12 12 12 15 24 24 24 24 27]
[0 0 3 3 6 12 12 15 15 18 24 24 27 27 30]
[0 0 3 3 6 12 12 15 15 18 24 24 27 27 30]

Backpack Problems in Leetcode

Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Solution in Go:

func canPartition(nums []int) bool {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if sum%2 == 1 {
		return false
	}
	V := sum / 2
	pack := make([]bool, V+1)
	pack[0] = true
	for _, n := range nums {
		for v := V; v >=n; v-- {
            if pack[v-n]{
                pack[v]=true
            }
        }
        if pack[V]{
            return true
        }
	}
	return false
}

Reuslt:
104 / 104 test cases passed.
Status: Accepted
Runtime: 4 ms
Memory Usage: 2.5 MB

Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

Solution in Go:

func coinChange(coins []int, amount int) int {
    if amount ==0{
        return 0
    }
    pack := make([]int, amount+1)
    for i := range pack {
		pack[i] = -1
	}
	pack[0] = 0
    for i := 1; i <= amount; i++ {
		for _, v := range coins {
			if v <= i && pack[i-v] != -1 {
				tmp := pack[i-v] + 1
				if pack[i] == -1 || pack[i] > tmp {
					pack[i] = tmp
				}
			}
		}
	}
    return pack[amount]
}

Reuslt:
104 / 104 test cases passed.
Status: Accepted
Runtime: 4 ms
Memory Usage: 2.5 MB