Dynamic Programming 1.3

Posted on | 0 comments
Words count in article 2451 | Reading time 12

Knapsack problem

鱼跃此时海,花开彼岸天

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, 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 possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively.

The knapsack problem has been studied for more than a century, with early works dating as far back as 1897. The name “knapsack problem” dates back to the early works of mathematician Tobias Dantzig (1884–1956), and refers to the commonplace problem of packing the most valuable or useful items without overloading the luggage.

Leetcode 322th 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
Note:
You may assume that you have an infinite number of each kind of coin.

Solution

DP

Input: Coins = [1, 2, 5], amount = 11

The minimum number of coins with a par value of 11 can be obtained from the minimum value of 33:

  1. The minimum number of coins with a coin value of 10 + the coin with a coin value of 1;

  2. The minimum number of coins with a coin value of 9 + the coin with a coin value of 2;

  3. The minimum number of coins with a coin value of 6 + the coin with a coin value of 5;

That is DP [11] = min (DP [10] + 1, DP [9] + 1, DP [6] + 1).

You can directly design the questions into a state.

  1. You need to know what is state in this problem, the subproblem is if now I have amount - coin, which coin can help me to get mininumber

  2. definite the function and table：you only need to consider how to get miniNumber with coins, 
     dp[amount] = min(1 + dp[amount - coins[i]]) for i in range(len(coins)) if coins[i] <= amount
  3. dp base:

if n == 0, dp[0] = 0 is mean I don’t need any coins to change

Dynamic_python

class Solution():
	def coinChange_dp(self, coins, amount):
		'''
		coins: list[int]
		amount: int
		rtype: int
		'''
		#special case
		if not coins or not amount:
			return 0
		#init dp
		dp = [float("inf")]*(amount + 1)
		#dp base
		dp[0] = 0
		for i in range(len(coins)):
			for j in range(coins[i], amount+1):
				#compare to every coins, if have one coin could make the mininumber
				dp[j] = min(1 + dp[j-coins[i]], dp[j])
		return dp[amount] if dp[amount] != float("inf") else -1

DFS+Alpha-beta

C program version

You could check here to see the recursive content. Dynamic_recursive_c

#include <stdio.h>
#include <stdlib.h>
#define min(a,b) ( (a)>(b) ? (b):(a) )/*返回最小值*/
#define random(x) (rand()%x)/*随机函数*/
#define INT_MAX 2147483647 /*最大值(随便定义的)*/
int retMin = INT_MAX;/*初始化retMin : 最少硬币数*/

/*逆序数组并从大到小排列*/
int cmpCoin(const void *a, const void *b) {
  int *ap = (int *)a;
  int *bp = (int *)b;

  return *bp - *ap;
}
/*DFS深度遍历+剪枝*/
void coinChange_dfs(int* coins, int coinsSize, int amount, int index, int c) {
  
  /*如果刚好凑够amount*/
  if (amount == 0) {
    retMin = min(c, retMin);
    return;
  }
  /*如果越界则返回*/
  if (index == coinsSize) return;
  
  for (int i = amount / coins[index]; i >= 0 && i+c < retMin; i --) {
    coinChange_dfs(coins, coinsSize, amount - i * coins[index], index+1, c+i);
  }

}
/*主函数
换零钱:用最少的硬币数换刚好的零钱
coins:面额不等的数组
coinsSize: coins数组的大小
amount: 所要交换的目标值总金额
*/
int coinChange(int* coins, int coinsSize, int amount){
  /*
  retMin : 最少硬币数
  */
  retMin = INT_MAX;
  /*如果数组为空,则立马返回-1*/
  if ((coins == NULL) || (coinsSize == 0)) {
    return -1;
  }
  /*如果amount为空,则立马返回0,表示不需要交换*/
  if (amount == 0) {
    return 0;
  }
  /*sorts an array对数组排序*/
  qsort(coins, coinsSize, sizeof(int), cmpCoin);
  /*打印数组*/
  for(int x = 0; x < coinsSize; x++){
    printf("coins = %d\n", coins[x]);
  }
  
  coinChange_dfs(coins, coinsSize, amount, 0, 0);
  /*如果最小硬币数依然等于最大值表示匹配不到零钱,返回-1,否则返回最小值*/
  return (retMin == INT_MAX) ? -1 : retMin;
}

int main()
{
  int coins[]={1,2,5};
  int amount = 8;
  printf("amount = %d\n", amount);
  int coinsSize = sizeof(coins) / sizeof(coins[0]);
  int res;
  res=coinChange(coins, coinsSize, amount);
  printf("res = %d",res);
  return 0;
}

Source code

My Github Code

背包问题

给定一组多个物品比如多面额的硬币或者产物，每种物品都有自己的重量和价值，在限定的总重量/总容量内，选择其中若干个（也即每种物品可以选0个或1个），设计选择方案使得物品的总价值最高。

Leetcode 322 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1
 

说明:
你可以认为每种硬币的数量是无限的。

方法

动态规划

输入: coins = [1, 2, 5], amount = 11 凑成面值为 11 的最小硬币数可以由以下 33 者的最小值得到：

1、凑成面值为 10 的最小硬币数 + 面值为 1 的这一枚硬币；

2、凑成面值为 9 的最小硬币数 + 面值为 2 的这一枚硬币；

3、凑成面值为 6 的最小硬币数 + 面值为 5 的这一枚硬币；

即 dp[11] = min (dp[10] + 1, dp[9] + 1, dp[6] + 1)。

可以直接把题目的问法设计成状态。

  1. 明确状态：这里的状态是指原问题和子问题中变化的变量，从问题出发,我们发现要凑成刚好的硬币数, 只有amount是可变的, 它可以当作状态, 因为硬币的个数是无限的，所以唯一的状态就是目标的金额amount。

  2. 定义dp数据/函数的含义：这里和定义递归函数是一样的，递归的一个非常重要的点就是：不去管函数的内部细节是如何处理的，我们只看其函数作用以及输入与输出。这里的含义就是指函数作用：我们定义一个dp数组，dp[n]表示当前目标金额是n，至少需要dp[n]个硬币凑出该金额。

  3. 明确选择：通过我们当前的选择来改变我们的状态,也就是我们的填表方式

Dynamic_python

class Solution():
	def coinChange_dp(self, coins, amount):
		'''
		coins: list[int]
		amount: int
		rtype: int
		'''
		#special case
		if not coins or not amount:
			return 0
		#init dp
		dp = [float("inf")]*(amount + 1)
		#dp base
		dp[0] = 0
		for i in range(len(coins)):
			for j in range(coins[i], amount+1):
				#compare to every coins, if have one coin could make the mininumber
				dp[j] = min(1 + dp[j-coins[i]], dp[j])
		return dp[amount] if dp[amount] != float("inf") else -1

DFS+剪枝

Python版

Dynamic_dfs_python

class Solution():
	def coinChange_dfs(self, coins, amount):
		if not amount or not coins:
			return 0
		l = len(coins)
		#从大到小排列
		coins.sort(reverse = True)
		#初始化最少硬币数为最大值
		self.res = amount + 1
		def dfs(balance, index, c):
			'''
			balance: int 剩余金额
			coins:   int 数组长度
			index:   int coins下标
			c:       int 此时的硬币数
			'''
			#如果余额为0,说明刚好凑成总金额,返回最小值
			if balance == 0:
				self.res = min(c, self.res)
				return
			#如果指针index从底部到顶部又回到底部,则返回
			if index == len(coins):
				return
			for i in range(balance/coins[index], -1, -1):
				#如果此时硬币数小于则继续遍历
				if i + c < self.res:
					dfs(balance - i*coins[index], index + 1, c+i)
				#如果是大于,则直接返回
				else:
					break
		#从最大面值开始递归
		dfs(amount, 0, 0)
		return self.res if self.res != amount + 1 else -1
C语言版

Dynamic_recursive_c

#include <stdio.h>
#include <stdlib.h>
#define min(a,b) ( (a)>(b) ? (b):(a) )/*返回最小值*/
#define random(x) (rand()%x)/*随机函数*/
#define INT_MAX 2147483647 /*最大值(随便定义的)*/
int retMin = INT_MAX;/*初始化retMin : 最少硬币数*/

/*逆序数组并从大到小排列*/
int cmpCoin(const void *a, const void *b) {
  int *ap = (int *)a;
  int *bp = (int *)b;

  return *bp - *ap;
}
/*DFS深度遍历+剪枝*/
void coinChange_dfs(int* coins, int coinsSize, int amount, int index, int c) {
  
  /*如果刚好凑够amount*/
  if (amount == 0) {
    retMin = min(c, retMin);
    return;
  }
  /*如果越界则返回*/
  if (index == coinsSize) return;
  
  for (int i = amount / coins[index]; i >= 0 && i+c < retMin; i --) {
    coinChange_dfs(coins, coinsSize, amount - i * coins[index], index+1, c+i);
  }

}
/*主函数
换零钱:用最少的硬币数换刚好的零钱
coins:面额不等的数组
coinsSize: coins数组的大小
amount: 所要交换的目标值总金额
*/
int coinChange(int* coins, int coinsSize, int amount){
  /*
  retMin : 最少硬币数
  */
  retMin = INT_MAX;
  /*如果数组为空,则立马返回-1*/
  if ((coins == NULL) || (coinsSize == 0)) {
    return -1;
  }
  /*如果amount为空,则立马返回0,表示不需要交换*/
  if (amount == 0) {
    return 0;
  }
  /*sorts an array对数组排序*/
  qsort(coins, coinsSize, sizeof(int), cmpCoin);
  /*打印数组*/
  for(int x = 0; x < coinsSize; x++){
    printf("coins = %d\n", coins[x]);
  }
  
  coinChange_dfs(coins, coinsSize, amount, 0, 0);
  /*如果最小硬币数依然等于最大值表示匹配不到零钱,返回-1,否则返回最小值*/
  return (retMin == INT_MAX) ? -1 : retMin;
}

int main()
{
  int coins[]={1,2,5};
  int amount = 8;
  printf("amount = %d\n", amount);
  int coinsSize = sizeof(coins) / sizeof(coins[0]);
  int res;
  res=coinChange(coins, coinsSize, amount);
  printf("res = %d",res);
  return 0;
}

参考

  1. 知乎 0-1背包问题的动态规划算法
  2. leetcode 题解

源码

My Github Code