基础DP（硬币问题）

95 阅读 0 评论 63 点赞

我是靠谱客的博主甜美雪碧，这篇文章主要介绍基础DP（硬币问题），现在分享给大家，希望可以做个参考。

n个硬币,面值v1 v2 v3...输入金额求最少组合数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;
public class Coin1 {
//最少硬币组合
public static int Money=251;
public static int [] type= {1,5,10,25,50};
public static int[] Min=new int[Money];
public static int[] Min_path=new int[Money];
public static void solve()
{
for(int k=0;k<Money;k++)
{
Min[k]=65535;
}
Min[0]=0;
for(int j=0;j<5;j++)
{
for(int i=type[j];i<Money;i++)
{
if(Min[i]>Min[i-type[j]]+1)
{
Min_path[i]=type[j];
Min[i]=Min[i-type[j]]+1;
}
}
}
}
public static void print_ans(int s)//打印硬币组合
{
while(s!=0) {
System.out.print(Min_path[s]+" ");
s=s-Min_path[s];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int s;
solve();
Scanner sc=new Scanner(System.in);
while((s=sc.nextInt())!=0) {
System.out.println("最少"+Min[s]+"个");//输出最少硬币个数
print_ans(s);//打印硬币组合
}
}
}

求每种金额对应的组合数

dp[i][j]:金额为i,j个硬币

dp[i][j]=dp[i][j]+dp[i-type[k]][j-1];

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.Scanner;
//最多100个硬币
//相比Coin1有限制多了一个硬币数维度
public class Coin0 {
public static int Money=251;//最多不超过250块
public static int COIN=101;//最多不超过100
public static int [] type= {1,5,10,25,50};
public static int[][] dp=new int[Money][COIN];
public static void solve() {
dp[0][0]=1;
for(int i=0;i<5;i++)
{
for(int j=1;j<COIN;j++)
{
for(int k=type[i];k<Money;k++)
{
dp[k][j]+=dp[k-type[i]][j-1];//面额k 硬币数j
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int s;
int[] ans=new int[Money];//记录每种面额对应的组合数
solve();
for(int i=0;i<Money;i++)
{
for(int j=0;j<COIN;j++)
{
ans[i]+=dp[i][j];
}
}
Scanner sc=new Scanner(System.in);
while((s=sc.nextInt())>0)
{
System.out.println(ans[s]);
}
}
}