# Baekjun 12865 Backpack Problem

Asked 1 weeks ago, Updated 1 weeks ago, 1 views

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

2022-09-19 23:32

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

2022-09-19 23:32

Popular Tags
python x 1174
android x 247
c x 235
java x 192
javascript x 106
mysql x 30
html x 27
node.js x 24
php x 21
list x 19