백준 1535 안녕

Dp의 냅색부터 잘해보자아아아아

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

기초적으로 knapsack은

1개씩 사용하는거와 여러개 사용하는 경우가있다

1개씩 사용한다는걸 생각하면

2중포문으로 구성한다음

n개의 데이터를 가지고 Max치부터 해당 weight 까지 돌리면된다

코드로 구성하면

for(int i=0;i<n;i++) {
	for(int j=max;j>weight[i];j--) {
    	Result[j] = Math.max(Result[j],Result[j-weight[i]]+value[i])
    }
}

하지만 여러번 사용하면 weight부터 시작해서 max까지 반대로 for문을잡아준다.

for(int i=0;i<n;i++) {
	for(int j=weight[i];j<=max;j++) {
    	Result[j] = Math.max(Result[j],Result[j-weight[i]]+value[i])
    }
}

그러면 해당문제에 적용해보자.

import java.io.*;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class 안녕 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		int[] L = new int[t];
		int[] J = new int[t];
		int[] result = new int[101];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<t;i++) {
			
			L[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<t;i++) {
			J[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=0;i<t;i++) {
			for(int j=100;j>L[i];j--) {
				result[j] = Math.max(result[j], result[j-L[i]]+J[i]);
			}
		}
		System.out.println(result[100]);
		
	}

}

결과