【java】硬币问题

87 阅读 0 评论 58 点赞

我是靠谱客的博主辛勤爆米花，这篇文章主要介绍【java】硬币问题，现在分享给大家，希望可以做个参考。

有n种硬币，面值分别为V1,V2,...,Vn，每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最大值和最小值。1<=n<=100,0<=S<=10000,1<=Vi<=S。

分析：本题的本质也是DAG上的路径问题。设d(i)表示"从结点i出发到结点0的最长路径"，则d(i)=max[d(i-Vj)+1]，最终答案就是d(S)。

先输入n和S分别代表硬币种类和目标面值，再输入n行数据，分别代表每种硬币的面值，输出硬币数目最多的方案。

样例输入：

3 7
2
3
4

样例输出：

2
2
3

复制代码

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
46
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int dpSolution(int s,int[] v,int[] d){
if(d[s]>=0)
return d[s];
if(s==0){
d[s]=0;
return 0;
}
for(int i=0;i<v.length;i++){
if(s-v[i]>=0){
int temp=dpSolution(s-v[i], v, d);
if(temp+1>d[s]){
d[s]=temp+1;
}
}
}
return d[s];
}
public static void print(int s,int[] v,int[] d){
for(int i=0;i<v.length;i++){
if(s-v[i]>=0&&d[s]-d[s-v[i]]==1){
System.out.println(v[i]);
print(s-v[i],v,d);
break;
}
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext())
{
int n=scanner.nextInt();
int s=scanner.nextInt();
int[] v=new int[n];
int[] d=new int[s+1];
Arrays.fill(d, -1);
for(int i=0;i<n;i++)
v[i]=scanner.nextInt();
dpSolution(s, v, d);
print(s,v,d);
}
scanner.close();
}
}

如果要求最小、最大两个值，记忆化搜索就必须写两个。在这种情况下，递推法更加方便。

先输入n和S分别代表硬币种类和目标面值，再输入n行数据，分别代表每种硬币的面值，先输出硬币数目最少的方案，再输出硬币数目最多的方案。

样例输入：

3 7
2
3
4

样例输出：

3
4

2
2
3

复制代码

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
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void print(int s,int[] v,int[] d){
for(int i=0;i<v.length;i++){
if(s-v[i]>=0&&d[s]-d[s-v[i]]==1){
System.out.println(v[i]);
print(s-v[i],v,d);
break;
}
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext())
{
int n=scanner.nextInt();
int s=scanner.nextInt();
int[] v=new int[n];
for(int i=0;i<n;i++)
v[i]=scanner.nextInt();
int[] min=new int[s+1];
int[] max=new int[s+1];
Arrays.fill(min, 100000);
Arrays.fill(max, -100000);
min[0]=0;
max[0]=0;
for(int i=1;i<=s;i++){
for(int j=0;j<n;j++){
if(i>=v[j]){
if(max[i-v[j]]+1>max[i])
max[i]=max[i-v[j]]+1;
if(min[i-v[j]]+1<min[i])
min[i]=min[i-v[j]]+1;
}
}
}
print(s,v,min);
System.out.println();
print(s,v,max);
}
scanner.close();
}
}