| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 550742 | PikaChu999 | Knapsack (NOI18_knapsack) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
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 Main{
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;
}
}