제출 #762877

#제출 시각아이디문제언어결과실행 시간메모리
762877Oz121Knapsack (NOI18_knapsack)Java
0 / 100
90 ms10152 KiB
import java.io.*; import java.util.*; public class knapsack { public static void main(String[] args) throws IOException { BufferedReader scan = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer l1 = new StringTokenizer(scan.readLine()); int W = Integer.parseInt(l1.nextToken()); int num = Integer.parseInt(l1.nextToken()); int[][] arr = new int[num][3]; for (int i = 0;i<num;i++) { StringTokenizer st = new StringTokenizer(scan.readLine()); arr[i][0] = Integer.parseInt(st.nextToken()); arr[i][1] = Integer.parseInt(st.nextToken()); arr[i][2] = Integer.parseInt(st.nextToken()); } Arrays.sort(arr,(a,b)->a[1]==b[1] ? b[0]-a[0] : a[1]-b[1]); printMat(arr); //Arrange by the weight. ArrayList<Pair> weights = new ArrayList<>(); int idx = 0; for (int i = 1;i<W+1;i++) { ArrayList<Pair> temp = new ArrayList<>(); while (idx<num&&arr[idx][1]==i) { int max = (int) Math.floor((double) W/i); if (temp.size()<max) { for (int j = 0;j<arr[idx][2]&&temp.size()<max;j++) temp.add(new Pair (arr[idx][1],arr[idx][0])); } idx++; } for (int j = 0;j<temp.size();j++) { weights.add(temp.get(j)); } } //System.out.println(weights); int size = weights.size(); int[][] dp = new int[size][W+1]; dp[0][weights.get(0).weight] = weights.get(0).val; for (int i = 1;i<size;i++) { for (int j = 0;j<=W;j++) { dp[i][j] = dp[i-1][j]; if (j-weights.get(i).weight>=0) { dp[i][j] = Math.max(dp[i][j],dp[i-1][j-weights.get(i).weight]+weights.get(i).val); } } } int ans = -1; for (int j = 0;j<=W;j++) { ans = Math.max(ans,dp[size-1][j]); } System.out.println(ans); } public static class Pair { int weight; int val; Pair (int weight, int val){ this.weight = weight; this.val = val; } @Override public String toString() { return weight+" "+val; } } public static void printMat (int[][] arr) { for (int i = 0;i<arr.length;i++) { for (int j = 0;j<arr[0].length;j++) { System.out.print(arr[i][j]+" "); } System.out.println(); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...