동적계획법: 배낭문제(아이템 수량제한 없음)


무게제한이 W, 아이템 종류가 N 이며 각각의 아이템 수량제한이 없는 경우

> 점화식은 가용한 무게W의 경우 최대값 ks(W) 는 i 아이템(무게 Wi, 가치 Pi)를 추가 한 것

ks(W) = max( ks(W -Wi) + Pi 



입력:

4 14 

2 40 

5 110 

10 200 

3 50


import java.util.Scanner;


public class Main {


static int[] w,p,m;// w 무게, p 가격, m 동적계획법 저장

static int N;//아이템 갯수

static int W;//허용 무게

public static void main(String[] args) {

//input

System.setIn(Main.class.getResourceAsStream("./input.txt"));

Scanner sc = new Scanner(System.in);

N = sc.nextInt();

W = sc.nextInt();


w = new int[N];

p = new int[N];

m = new int[W+1];//동적계획법 저장

for(int i=0; i < N; ++i){

w[i] = sc.nextInt();

p[i] = sc.nextInt();

}

int result = ks(W);

//output

System.out.println(result);

}

static int ks(int weight){

if(m[weight] > 0) {

return m[weight];

}

int max = 0;

for(int i = 0; i < N; ++i){

if(weight - w[i] < 0) {

continue;

}

max = Math.max(max, ks(weight - w[i]) + p[i]);

}

m[weight] = max;

return max;

}


}