应该是0-1背包问题吧 :这样不知行不行。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); int n = Integer.parseInt(sc.nextLine()); int sum =0 ; int[] data = new int[n]; for (int i = 0; i < n ; i++) {
data[i] = sc.nextInt(); sum +=data[i]; } int m = sc.nextInt(); Arrays.sort(data); if (m<0||data[0]>m||sum<m) System.out.println("-1"); int[][] dp = new int[n+1][m+1]; for (int i = 0; i <=m ; i++) {
dp[0][i] = 1; } for (int i = 0; i <dp.length; i++) {
dp[i][0] = 1; } for (int i = 1; i <n+1 ; i++) { for (int j = 1; j <=m ; j++) { if (j >=data[i-1]) dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-data[i-1]]*data[i-1]); else dp[i][j] = dp[i-1][j]; }
}
System.out.println(dp[n][m]); }