java完成 给定一组正整数数组M,找出M数组中N项和为给定数S。如果有多对N项数字的和都等于 S,则输出N个数的乘积最小的哪一项,没有则返回空;
时间: 2024-03-01 22:54:40 浏览: 76
java 输入一个数字组成的数组(输出该数组的最大值和最小值)
以下是Java的实现代码:
```java
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] M = {1, 2, 3, 4, 5, 6};
int S = 10;
int N = 3;
int minProduct = findMinProduct(M, S, N);
if (minProduct == -1) {
System.out.println("没有找到符合条件的解");
} else {
System.out.println("乘积最小的一组解为:" + minProduct);
}
}
public static int findMinProduct(int[] M, int S, int N) {
Arrays.sort(M); // 排序
int i = 0, j = M.length - 1, minProduct = Integer.MAX_VALUE;
while (i < j) {
if (M[i] + M[j] == S) {
if (N == 2) {
minProduct = Math.min(minProduct, M[i] * M[j]);
i++;
j--;
} else {
// 递归查找剩余的N-2个数
int[] subM = Arrays.copyOfRange(M, i + 1, j);
int subMinProduct = findMinProduct(subM, S - M[i] - M[j], N - 2);
if (subMinProduct != -1) {
minProduct = Math.min(minProduct, M[i] * M[j] * subMinProduct);
}
i++;
}
} else if (M[i] + M[j] < S) {
i++;
} else {
j--;
}
}
return minProduct == Integer.MAX_VALUE ? -1 : minProduct;
}
}
```
其中,M是正整数数组,S是目标和,N是要求的项数。如果找到了一组解,则返回它们的乘积;否则返回-1。
阅读全文