【深基12.例1】部分背包问题 Java

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int t = sc.nextInt();Integer[] s = new Integer[n]; // 存排序后的索引值int[] m = new int[n]; // 重量int[] v = new int[n]; // 价值for (int i = 0; i < n; i++) {s[i] = i; // 填充索引值}for (int i = 0; i < n; i++) {m[i] = sc.nextInt();v[i] = sc.nextInt();}// 性价比从高到低排序Arrays.sort(s, (a, b) -> {double r1 = (double) v[a] / m[a];double r2 = (double) v[b] / m[b];return Double.compare(r2, r1);});double ans = 0;for (int i = 0; i < n; i++) {if (t - m[s[i]] >= 0) {t -= m[s[i]];ans += v[s[i]];} else {ans += (double) v[s[i]] / m[s[i]] * t; // 剩余容量塞满break;}}System.out.printf("%.2f", ans);}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~