【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

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

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();
}
}

最后

以上就是辛勤爆米花为你收集整理的【java】硬币问题的全部内容，希望文章能够帮你解决【java】硬币问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。