由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 这道硬币找零题有好的DP解法么?
相关主题
刚刚A 家第三电面悲剧。贡献两题。有人做hackranker的题么
上一道题hackerrank的xor题目
这个字符串题有什么好的解法?好吧,继续hackerrank讨论。weekly contest, walking on grids
关于什么时候可以用贪心算法求找零问题问道硬币题目
再问Maximal Rectangle的N^2解法topercode DP问题求解
求G加一题的线性解法求教:这两道题有什么陷阱吗?
问一个G家面试题Another DP Problem: Balanced Partition
用各种硬币组合sum的问题是不是该用DP啊?这两道leetcode题有更好的答案吗?
相关话题的讨论汇总
话题: int话题: dp话题: arr话题: 硬币话题: total
进入JobHunting版参与讨论
1 (共1页)
K*******i
发帖数: 399
1
有25分,10分,5分和1分四种硬币,假定每种硬币都有无限个。给定一个找零的分值N,求不同的找法。递归比较容易,那么如何用DP?
比如说N = 11,共四种找法:
10 * 1 + 1 * 1
5 * 2 + 1 * 1
5 * 1 + 1 * 6
1 * 11
想用DP,状态转移方程如下
F(0) = 1;
F(n) = {F(n - 25), n >= 25} + {F(n - 10), n >= 10} + {F(n - 5), n >= 5} + {F(n - 1), n >= 1}
也就是
F(11) = F(1) + F(6) + F(10)
但是却发现有重复
F(6)的解包含5 * 1 + 1 * 1
在这基础上添加一个五分硬币得到5 * 2 + 1 * 1
F(10)的解包含5 * 2
在这基础上添加一个一分硬币得到5 * 2 + 1 * 1
这样就重复计算了
Z*****Z
发帖数: 723
2
把所有硬币放在一个数组c里面。然后函数F[i,j]代表用前i个硬币摆出value j的摆法。
初始F[*,*] = 0
然后F[i,j] = sum(F[i-1, j - k * c[i]]) 0 <= k <= j/c[i]
实现起来可以用背包九讲里面第二讲的方法:
F[i,j] = F[i, j - c[i]] + F[i-1, j]
代码:
package common.knapsack;
public class Complete {
public static void main(String[] args) {
int[] in = {1, 5, 10, 25};
System.out.println(howMany(in, 11));
}
//How many ways to pack

public static int howMany(int[] arr, int n){

int[] A = new int[arr.length + 1];
System.arraycopy(arr, 0, A, 1, arr.length);

int[] dp = new int[n + 1];

for(int i = 1; i < A.length; i ++){
for(int j = A[i]; j <= n; j ++){

dp[j] += (j == A[i]) ? 1 : dp[j - A[i]];
}
}

return dp[n];
}
}

N,求不同的找法。递归比较容易,那么如何用DP?
{F(n - 1), n >= 1}

【在 K*******i 的大作中提到】
: 有25分,10分,5分和1分四种硬币,假定每种硬币都有无限个。给定一个找零的分值N,求不同的找法。递归比较容易,那么如何用DP?
: 比如说N = 11,共四种找法:
: 10 * 1 + 1 * 1
: 5 * 2 + 1 * 1
: 5 * 1 + 1 * 6
: 1 * 11
: 想用DP,状态转移方程如下
: F(0) = 1;
: F(n) = {F(n - 25), n >= 25} + {F(n - 10), n >= 10} + {F(n - 5), n >= 5} + {F(n - 1), n >= 1}
: 也就是

p*****2
发帖数: 21240
3
先用recursion+cache的DP,再想bottom up的DP应该就会容易了。
p*****2
发帖数: 21240
4
写了一个topdown dp的。
import java.io.*;
import java.util.*;
public class Coin
{
public static void main(String[] args)
{
new Coin().run();
}
PrintWriter out = null;
int[][] dp = null;
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
int[] arr = new int[]
{ 25, 10, 5, 1 };
int n = 11;
dp = new int[arr.length][n + 1];
for (int i = 0; i < arr.length; i++)
Arrays.fill(dp[i], -1);
int ans = dfs(arr, 0, n);
out.println(ans);
out.close();
}
int dfs(int[] arr, int start, int value)
{
if (value == 0)
return 1;
if (start == arr.length)
return 0;
if (dp[start][value] != -1)
return dp[start][value];
int total = 0;
for (int i = 0; i * arr[start] <= value; i++)
{
total += dfs(arr, start + 1, value - i * arr[start]);
}
dp[start][value] = total;
return total;
}
}
p*****2
发帖数: 21240
5
然后再写bottomup的就容易了。
int bottomup(int[] arr, int n)
{
int m = arr.length;
dp = new int[2][n + 1];
dp[0][0] = 1;
dp[1][0] = 1;
for (int j = 1; j <= n; j++)
{
if (j % arr[0] == 0)
dp[0][j] = 1;
else
dp[0][j] = 0;
}
for (int i = 1; i < m; i++)
{
int curr = i % 2;
int prev = (i - 1) % 2;
for (int j = 1; j <= n; j++)
{
int total = 0;
for (int k = 0; k * arr[i] <= j; k++)
{
total += dp[prev][j - k * arr[i]];
}
dp[curr][j] = total;
}
}
return dp[(m - 1) % 2][n];
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
这两道leetcode题有更好的答案吗?再问Maximal Rectangle的N^2解法
facebook hackercup里的一道题求G加一题的线性解法
都说CC150有错误,请问具体都哪些题有错误呢?问一个G家面试题
这个题有什么好方法吗?用各种硬币组合sum的问题是不是该用DP啊?
刚刚A 家第三电面悲剧。贡献两题。有人做hackranker的题么
上一道题hackerrank的xor题目
这个字符串题有什么好的解法?好吧,继续hackerrank讨论。weekly contest, walking on grids
关于什么时候可以用贪心算法求找零问题问道硬币题目
相关话题的讨论汇总
话题: int话题: dp话题: arr话题: 硬币话题: total