백준 : 12865

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

0 - 1 냅색 문제이다.

dp[i][k] = max(dp[i-1][k],dp[i-1][k-Weight[i]]) 이다.

물건은 하나밖에없다 . 따라서 배낭에 하나넣으면 같은 물건은 더넣을수가 없는 전제이다. 

그래서 0 - 1 냅색  

dp는 1~N 까지의 물건들을 배낭에 넣을때 

1. 현재 넣을수 있는가 없는가를 판단한다 넣을수없다면 dp[i-1][j] 가 최대치가 된다.

2. 현재물건을 넣을수 있다면 dp[i-1][j] 이전 재료들로 뽑앗던 최대치와 dp[i-1][j-weight[i]] + P[i] 이전 재료에서 현재물건을 넣을수 있는 공간을 뺀 최대치와 현재물건의 가치의 합중에 더큰것을 선택하면 가장 큰 가치의 물건을 뽑을수가 있다.

package day0301;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B12865 {
    static int Weight[];
    static int P[];
    static int dp[][];
    static int N,K;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        P = new int[N+1];
        dp = new int[N+1][K+1];
        Weight = new int[N+1];
        for(int n=1;n<=N;n++) {
            st = new StringTokenizer(br.readLine());
        
            Weight[n] = Integer.parseInt(st.nextToken()); 
            P[n] = Integer.parseInt(st.nextToken()); 
        }
        
        for(int i=1;i<=N;i++) {
            
            for(int k=1;k<=K;k++) {
                if(Weight[i] > k) {
                    dp[i][k] = dp[i-1][k];
                }else {
                    dp[i][k] = Math.max(dp[i-1][k], dp[i-1][k-Weight[i]]+P[i]);
                }
            }
            
        }
        
        System.out.println(dp[N][K]);
        
    }
}