The first line is given the number of articles N (1 ) N 100 100) and the weight K (1 K K 100 100,000) that Junseo can withstand. From the second line through N lines, each item is given a weight W (1 ,000 W 물건 100,000) and a value V (0 V V 1,000 1,000). It outputs the maximum value of the sum of the values of items that can be put in a backpack in one line. Any number given as an input is an integer.
Enter: 4 7 6 13 4 8 3 6 5 12 Answer: 14
In Eclipse, the answer 14 is printed, but Baekjun said it was wrong if you grade it. Is it my first time to play dp, so I wonder if I went back to Yamae... Where should I modify it?
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int N=in.nextInt();
int K=in.nextInt();
if((N<1||N>=101)||(K<1||K>=100001)) {
N=in.nextInt();
K=in.nextInt();
}
int[] W=new int[N];
int[] V=new int[N];
for(int i=0;i<N;i++) {
W[i]=in.nextInt();
V[i]=in.nextInt();
}
int[][] dp=new int[N+1][K+1];
int MaxValue=0;
for(int n=1;n<=N;n++) {
for(int k=0;k<=K;k++) {
dp[n][k]=0;
if(k==W[n-1]) {
dp[n][k]=V[n-1];
}
if(k>W[n-1]) {
dp[n][k]=Math.max(dp[n][k-W[n-1]]+V[n-1],dp[n-1][k]);
}
MaxValue=Math.max(MaxValue,dp[n][k]);
}
}
System.out.println(MaxValue);
}
}
java
It would be helpful if you check the two cases below in order.
2 100 1 1 1 1
4 3 1 1 1 1 2 1 1 3
© 2024 OneMinuteCode. All rights reserved.