'2016/03'에 해당되는 글 2건

  1. 2016.03.19 동적계획법: 배낭문제(아이템 수량제한 없음)
  2. 2016.03.19 최대공약수, 최소공배수

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


무게제한이 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;

}


}




최대공약수, 최소공배수


유클리드 호제법을 사용하여 최대공약수를 구함

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95




public class Main {


public static void main(String[] args) {


int g = gcd(78696, 19332); //유클리드 호제법 사용

System.out.println(g);//36


int l = lcm(78696, 19332);

System.out.println(l);//42259752

}


static int gcd(int p, int q) {

if(q == 0) return p;

return gcd(q, p%q);

}

static int lcm(int A, int B){

int g = gcd(A,B);

int a = A/g;

int b = B/g;

return g*a*b; //최소공배수

}

}