Submission #550743

#	Time	Username	Problem	Language	Result	Execution time	Memory
550743		PikaChu999	Knapsack (NOI18_knapsack)	Java	100 / 100	782 ms	73036 KiB

knapsack

/*
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1

value, weight, copies
*/
import java.util.*;
import java.io.*;

public class knapsack{
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer details = new StringTokenizer(br.readLine());
    int capacity = Integer.parseInt(details.nextToken()); //capacity of shopping basket
    int n = Integer.parseInt(details.nextToken()); //number of types of shopping items 
    ArrayList<Item>[] items = new ArrayList[capacity + 1]; //sorted by weight and then value (largest to smallest value)
    for(int a = 0; a <= capacity; a++) items[a] = new ArrayList<Item>();
    for(int a = 0; a < n; a++){
      StringTokenizer ite = new StringTokenizer(br.readLine()); //value, weight and copies
      long val = Long.parseLong(ite.nextToken());
      int weight = Integer.parseInt(ite.nextToken());
      int copies = Integer.parseInt(ite.nextToken());
      items[weight].add(new Item(val, copies));
    }
    for(int a = 0; a <= capacity; a++) Collections.sort(items[a]);
    //System.out.println(Arrays.toString(items));

    long[][] dp = new long[capacity + 1][capacity + 1]; //dp[a][b], where dp[a][b] is the max value that you can get given a capacity of i and all items with weight b or less     
    for(long[] row : dp) Arrays.fill(row, -1000000000000000L);
    dp[0][0] = 0; 
    long max = 0; 
    for(int maxWeight = 1; maxWeight <= capacity; maxWeight++){
      for(int cp = 0; cp <= capacity; cp++){
        long sm = 0; 
        int capacityTaken = 0; 
        dp[maxWeight][cp] = dp[maxWeight - 1][cp];
        for(Item i : items[maxWeight]){
          for(int cur = 0; cur < i.copies; cur++){
            capacityTaken += maxWeight; 
            sm += i.value;
            if(capacityTaken > cp) break; 
            dp[maxWeight][cp] = Math.max(dp[maxWeight][cp], dp[maxWeight - 1][cp - capacityTaken] + sm);
          }
          if(capacityTaken > cp) break; 
        }
        max = Math.max(max, dp[maxWeight][cp]);
      }
    }
    System.out.println(max);
    br.close();
  }
}
class Item implements Comparable<Item>{
  long value; 
  int copies; 
  public Item(long v, int c){
    value = v; 
    copies = c; 
  }
  public String toString(){
    return value + " " + copies; 
  }
  public int compareTo(Item i){
    if(i.value > value) return 1; 
    if(i.value < value) return -1; 
    return copies - i.copies; 
  }
}

Compilation message (stderr)

Note: knapsack.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27