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

1 Answers

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

If you have any answers or tips


© 2022 pinfo. All rights reserved.