java查找生成给定值的包的最小数量
我正在尝试解决类似于此问题的问题,但进行了一些修改:
“给定一个值V,如果我们想换V美分,并且我们有无限量的C={C1,C2,…,Cm}值硬币,那么换硬币的最小数量是多少?”
Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents
在我的例子中,我有一个对象数组,而不仅仅是一个数字数组。每件物品都有数量和价格。 我想打印构成给定数量的最小数量的对象,然后打印价格,类似于:
2 x 5 9.95
1 x 3 5.95
我使用了此代码,但找不到如何完成任务:
public static void main(String[] args) {
Product croissant = new Product("Croissant", "CF", null);
Pack CF_1 = new Pack(3, 5.95);
Pack CF_2 = new Pack(5, 9.95);
Pack CF_3 = new Pack(9, 16.99);
croissant.addPack(CF_1);
croissant.addPack(CF_2);
croissant.addPack(CF_3);
System.out.println(minCoins(croissant, 13));
}
static int minCoins(Product product, int V) {
// table[i] will be storing
// the minimum number of coins
// required for i value. So
// table[V] will have result
int table[] = new int[V + 1];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for (int i = 1; i <= V; i++)
table[i] = Integer.MAX_VALUE;
// Compute minimum coins required for all
// values from 1 to V
for (int i = 1; i <= V; i++) {
// Go through all coins smaller than i
for (Pack pack : product.packList) {
if (pack.qty <= i) {
int sub_res = table[i - pack.qty];
if (sub_res != Integer.MAX_VALUE
&& sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
}
return table[V];
}
# 1 楼答案
你可以得到一个列表,里面列出了最低硬币数量,如下所示:
从给定的
V
开始,然后查找表的值小于1
的包,因为要达到V
,必须在某个地方有一个小于1
的值。如果你找到了一个,将它添加到列表中,并将下一个V
减少你找到的包的数量,然后继续代码是:
以
V
=13
为例,列表如下:[{3, 5.95}, {5, 9.95}, {5, 9.95}]
这是假设您将Pack
类的toString()
实现为如果您想使用^{} ,可以将列表缩减为地图
比如:
list.stream().collect(Collectors.groupingBy(Pack::getQty))