求个出发票算法

Question

目前有面额100元，50元，30元，20元的发票并且库存有限，有某笔消费金额为total元，
求给出张数之和最小的发票组合?抽象成java代码如下
HashMap<Integer,Long> invoiceMap=new HashMap<Integer,Long>()//存放发票面额和库存
invoiceMap.put(30,10L);
invoiceMap.put(50,3L);
invoiceMap.put(20,5L);
invoiceMap.put(100,10L);
int total=130;
HashMap<Integer,Long> result=invoiceMethod(invoiceMap,total);
求实现这个方法invoiceMethod(invoiceMap,total)？

Answer 1

楼主你还记得咋样获得1234的个位十位百位千位不？用%，/，（你还记得大名湖畔的xxxx?哈哈哈哈）

Answer 2

http://www.fendouzhai.com/?action-viewnews-itemid-182
硬币找零问题描述：现存在一堆面值为 V1、V2、V3 … 个单位的硬币，问最少需要多少个硬币才能找出总值为 T 个单位的零钱？假设这一堆面值分别为 1、2、5、21、25 元，需要找出总值 T 为 63 元的零钱。

Answer 3

int tatol=290;
//面值
Integer[] values={100,50,20,10};
//支出
HashMap<Integer, Integer> expenditure=new HashMap<Integer, Integer>();
//库存
HashMap<Integer, Integer> inventory=new HashMap<Integer, Integer>();
inventory.put(100, 10);
inventory.put(50, 15);
inventory.put(20, 20);
inventory.put(10, 30);

for (int i = 0; i < values.length; i++) {
//当前计算的面值
int value=values[i];
//余额
int x=tatol/value;

//判断库存
if(inventory.get(value)>x){
expenditure.put(value, x);
inventory.put(value, inventory.get(value)-x);
}else{
expenditure.put(100, inventory.get(value));
inventory.put(value, 0);
}
//计算剩余要找的钱z
tatol-=value*expenditure.get(value);
}


System.out.println("100元:"+expenditure.get(100)+"张");
System.out.println("50元:"+expenditure.get(50)+"张");
System.out.println("20元:"+expenditure.get(20)+"张");
System.out.println("10元:"+expenditure.get(10)+"张");

Answer 4

public class Equals1 {
// 面值
    int[] values= {100,50,30,20};
    int[] zhangshu = {0,0,0,0};//张数
//  库存
    HashMap<Integer, Integer> invoiceMap=new HashMap<Integer, Integer>();
    int total = 150;
    public Equals1(){
     invoiceMap.put(30,3);
     invoiceMap.put(50,3);
     invoiceMap.put(20,5);
     invoiceMap.put(100,2);
    }
public int action(int index,int tail){
if(index>values.length - 1){
return -1;
}
zhangshu[index] = Math.min(tail/values[index],invoiceMap.get(values[index]));
tail -= zhangshu[index]*values[index];
if(tail==0){
return 0;
}
else{
for(int i= 0;i <=zhangshu[index];zhangshu[index]--){
 if(action(index+1,tail)==0){
 return 0;
 }
 tail += values[index];
}
}
return tail;
}
public static void main(String[] args) {
Equals1 a = new Equals1();
int total = 500;
a.action(0,total);
if(a.action(0,total)==0){
for(Integer it:a.zhangshu){
System.out.print(it+" ");
}
}
else{
System.out.print("不能分配该数字。");
}
}
}

Answer 5

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;import org.junit.Test;public class FP {
HashMap<Integer, Long> invoiceMap = new HashMap<Integer, Long>();// 存放发票面额和库存 ArrayList<Integer> list = new ArrayList<Integer>(); public FP() {
invoiceMap.put(30, 10L);
invoiceMap.put(50, 3L);
invoiceMap.put(20, 5L);
invoiceMap.put(100, 10L); Set<Integer> set = invoiceMap.keySet();
Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
list.add(it.next());
}
Collections.sort(list);
Collections.reverse(list);
// int total = 130;
} public HashMap<Integer, Long> invoiceMethod(
HashMap<Integer, Long> invoiceMap, int total) { for (int i = 0; i < list.size(); i++) { if (total >= (Integer) list.get(i)) {
int count = total / list.get(i); // invoiceMap 的数值发生变化
invoiceMap
.put(list.get(i), invoiceMap.get(list.get(i)) - count);
// total 减少数据
total -= count * list.get(i);
}
}
return invoiceMap;
} private void pt(Object integer) {
System.out.println(integer);
} @Test
public void t() {
FP f = new FP();
invoiceMethod(invoiceMap, 150);
pt(invoiceMap);
}
}