这道硬币找零题有好的DP解法么？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这道硬币找零题有好的DP解法么？

这道硬币找零题有好的DP解法么？# JobHunting - 待字闺中

K*i2012-05-10 07:05

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*Z2012-05-10 07:05

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*22012-05-10 07:05

3 楼

先用recursion+cache的DP，再想bottom up的DP应该就会容易了。

p*22012-05-10 07:05

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*22012-05-10 07:05

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];
}