package test;
import java.util.Arrays;
import java.util.Stack;
//注意:本实例的所有注释都是以
//COINS = new int[] { 1, 2, 5}并且SUM = 10;
//为例子的
public class CoinToSum4{
private static final int[] COINS = new int[] { 1, 2, 5, 10, 20, 50 };
private static final int SUM = 100;
public static void main(String[] args) throws Exception {
System.out.println(System.currentTimeMillis());
calc2(SUM, COINS);
System.out.println(System.currentTimeMillis());// 80 ms
}
private static void calc2(int sum, int[] coins) {
Stack<Integer> stack = new Stack<Integer>();
Arrays.sort(coins);// 对数组升序排序
int currentSum = 0;// 当前栈中数据的和
int index = 0;// 下一个要进栈的数据在coins中的索引
int maxIndex = coins.length;// coins数组的最大索引
int cnt = 0;// 统计找到的组合数
stack.push(new Integer(coins[index]));// 先把最小的数据进栈
currentSum += coins[index];// 当前栈中数据的和递增
while (!stack.isEmpty()) {
// 当前栈中数据的和比sum小,则还要往栈里推送数值不小于栈顶元素的数据
if (currentSum < sum) {
int top = stack.peek();
index = getIndex(top, coins);
stack.push(new Integer(coins[index]));
currentSum += coins[index];
}
// 找到一组数据和为SUM
else if (currentSum == sum) {
cnt++;
// System.out.println("case: " + cnt + " " + stack);
// 比如此时的栈:1 1 1 1 2 2 2
// 或:5 5
int element = stack.pop();
currentSum -= element;
if (!stack.isEmpty()) {
int topData = stack.peek();// 获取栈顶元素
index = getIndex(topData, coins);
// 此时的栈:1 1 1 1 2 2 弹中栈顶元素2,并把比弹出的元素2大的下一个数据5推进栈
if (!stack.isEmpty() && stack.get(0) != coins[maxIndex - 1]) {
element = stack.pop();
currentSum -= element;
++index;// 下一个要进栈的数据,索引加1
stack.push(new Integer(coins[index]));// 此时的栈:1 1 1 1
// 2 5
currentSum += coins[index];
}
// 比如此时的栈:5 因为栈中的数据是从栈底向上递增的,当栈底为coins中的最大数据后,
// 说明已经找完了栈中数据和为sum的组合
else if (stack.get(0) == coins[maxIndex - 1]) {
System.out.println("totally " + cnt + " solutions.");
return;
}
}
} else if (currentSum > sum) {
// 比如此时的栈:1 1 1 5 5
// 或 1 1 1 1 1 2 2 2
int element = stack.pop();
currentSum -= element;
if (!stack.isEmpty()) {
int topData = stack.peek();
if ((index = getIndex(topData, coins)) != -1) {
++index;
// index 已到达最大索引,则要继续出栈
if (index >= maxIndex) {
// 比如此时的栈:1 1 1 5 栈顶连续出现coins数组的最大数据
// 则要一直退栈直到栈顶不是最大数据
while (!stack.isEmpty() && index >= maxIndex) {
element = stack.pop();
currentSum -= element;
if (!stack.isEmpty()) {
topData = stack.peek();
index = getIndex(topData, coins);
++index;
}
}
// 此时的栈:1 1 1 弹出栈顶元素1,并把比弹出的元素1大的下一个数据2进栈
if (!stack.isEmpty()) {
topData = stack.pop();
currentSum -= topData;
stack.push(new Integer(coins[index])); // 此时的栈:1
// 1 2
currentSum += coins[index];
}
} else {
// 此时栈:1 1 1 1 1 2 2 弹出栈顶元素2后,再把比弹出的元素2大的下一个数据5推进栈
element = stack.pop();
currentSum -= element;
index = getIndex(element, coins);
++index;
stack.push(new Integer(coins[index]));// 此时的栈:1 1
// 1 1 1 2 5
currentSum += coins[index];
}
}
}
}
}
}
/**
* 找出s在数组arr中的索引值
*
* @param s
* @param arr
* @return 若s不再数组arr中,则返回-1
*/
private static int getIndex(int s, int[] arr) {
for (int i = 0; i < arr.length; i++) {
if (s == arr[i]) {
return i;
}
}
return -1;
}
}
没有合适的资源?快使用搜索试试~ 我知道了~
确定将一定数量的钱比如100,换成1,2,5,10,20,50元的组合问题(4)
共1个文件
java:1个
需积分: 50 8 下载量 33 浏览量
2019-03-25
01:08:23
上传
评论
收藏 1KB RAR 举报
温馨提示
NULL 博文链接:https://hxz-qlh.iteye.com/blog/1141327
资源推荐
资源详情
资源评论
收起资源包目录
CoinToSum4.rar (1个子文件)
CoinToSum4.java 4KB
共 1 条
- 1
资源评论
weixin_38669628
- 粉丝: 383
- 资源: 6万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功