제출 #467823

#제출 시각아이디문제언어결과실행 시간메모리
467823rainliofficialKnapsack (NOI18_knapsack)Java
12 / 100
83 ms9440 KiB
import java.io.*; import java.util.*; public class knapsack { static int maxW, n; static Item[] arr; public static void main(String[] args) throws IOException{ BufferedReader file = new BufferedReader(new InputStreamReader(System.in)); //BufferedReader file = new BufferedReader(new FileReader("file.in")); StringTokenizer st = new StringTokenizer(file.readLine()); maxW = Integer.parseInt(st.nextToken()); n = Integer.parseInt(st.nextToken()); arr = new Item[n]; for (int i=0; i<n; i++){ st = new StringTokenizer(file.readLine()); arr[i] = new Item(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); } int[][] dp = new int[maxW+1][n+1]; for (int i=1; i<=maxW; i++){ for (int j=1; j<=n; j++){ for (int k=1; arr[j-1].weight*k<=i && k <= arr[j-1].k; k++){ if (i >= arr[j-1].weight*k){ dp[i][j] = Math.max(dp[i][j], dp[i-arr[j-1].weight*k][j-1] + arr[j-1].val*k); } } } } System.out.println(dp[maxW][n]); } static class Item{ int val, weight, k; public Item(int val, int weight, int k){ this.val = val; this.weight = weight; this.k = k; } } }
#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...