AcWing 532. 货币系统【简化货币系统】(Java 二维+一维)
原题链接
中等
作者:
Limited
,
2021-02-10 17:55:09
,
所有人可见
,
阅读 299
要点
- 理解:若某种面额的货币可以被其它面额的组成,则该货币是多余的,可以排除
- 如 货币【1,2,5】,其中5=1+1+1+1+1、2=1+1,所以面额2和5的货币可省略,系统简化为【1】
- 如果某种货币不能被其他货币组成(即必选),那么能组成该货币面额的方案仅1种
- 货币可不限次使用,原题转化为完全背包问题
- 记
n
为货币总数、a[i]
为第i
种货币的面额,当考虑所有种类货币且总面额恰好为a[i]
的选法方案总数(即f[n][a[i]]
)为1时,货币a[i]
必选
代码 二维
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int t, n;
static int[][] f = new int[110][25010];
static int[] a = new int[110];
public static void main(String[] args) {
t = scanner.nextInt();
for (int k = 1; k <= t; k++) {
// 货币面额存入数组 并升序排列
n = scanner.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt();
}
Arrays.sort(a, 1, n + 1);
// 初始化边界 只考虑前0种货币且其总价值恰好为0的选法方案总数为1 (什么都不选也是一种方案)
f[0][0] = 1;
// 完全背包问题 枚举到总价值为单货币最大面额(即排序后的a[n])即可
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= a[n]; j++) {
f[i][j] = f[i - 1][j];
if (j >= a[i]) {
f[i][j] += f[i][j - a[i]];
}
}
}
// 遍历结果数组 f[n][a[i]]表示考虑前n种(即所有)货币且总价值恰好为a[i](即某种货币面额)的选法方案总数
// 若方案数为1 则表示该面额只能由本种货币组成 所以本货币必选 ans++
int ans = 0;
for (int i = 1; i <= n; i++) {
if (f[n][a[i]] == 1) {
ans++;
}
}
System.out.println(ans);
}
}
}
空间优化到一维
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int t, n;
static int[] f = new int[25010];
static int[] a = new int[110];
public static void main(String[] args) {
t = scanner.nextInt();
for (int k = 1; k <= t; k++) {
n = scanner.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt();
}
Arrays.sort(a, 1, n + 1);
// 因为有多个测试案例 对于每个测试案例都要保证全新的f记录状态
Arrays.fill(f, 0);
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = a[i]; j <= a[n]; j++) {
f[j] += f[j - a[i]];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (f[a[i]] == 1) {
ans++;
}
}
System.out.println(ans);
}
}
}