https://algospot.com/judge/problem/read/PACKING#


문제 :


여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다. 


물건노트북 컴퓨터카메라XBOX365커피그라인더아령백과사전
부피4264210
절박도7106754
캐리어의 용량이 정해져 있기 때문에 가져갈 수 있는 물건들의 부피 합은 캐리어의 용량 w 이하여야 합니다. 이때 절박도를 최대화할 수 있는 물건들의 목록을 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 가져가고 싶은 물건의 수 N (1≤N≤100)과 캐리어의 용량 W (1≤W≤1000)가 주어집니다. 그 이후 N줄에 순서대로 각 물건의 정보가 주어집니다. 한 물건에 대한 정보는 물건의 이름, 부피, 절박도 순서대로 주어지며, 이름은 공백 없는 알파벳 대소문자 1글자 이상 20글자 이하의 문자열, 부피와 절박도는 1000 이하의 자연수입니다.

출력

각 테스트 케이스별 출력의 첫 줄에는 가져갈 수 있는 물건들의 최대 절박도 합과 가져갈 물건들의 개수를 출력합니다. 이후 한 줄에 하나씩 각 물건들의 이름을 출력합니다. 만약 절박도를 최대화하는 물건들의 조합이 여럿일 경우 아무 것이나 출력해도 좋습니다.


예제 입력

2
6 10
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4
6 17
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4

예제 출력

24 3
laptop
camera
grinder
30 4
laptop
camera
xbox
grinder



풀이 :


이 문제는 DP(Dynamic Programming) 문제로 유명하다는 Knapsack문제의 변형문제라고 한다. 


이 문제는 다르게 표현하면, 정해진 weight ( 즉, 캐리어의 용량 ) 내에서 최대 절박도를 구하는 문제다. 


구해야 하는 출력값에는 절박도, 물건 개수, 물건 이름이 있다. 


먼저 최대 절박도를 구해보자 .


간단 표현 식 :


findMaxHope ( 물건 리스트, 남은 캐리어 용량, 현재 아이템 ){

        # 기저부분

1. 현재 아이템이 마지막 아이템이면 나간다

2. 남은 용량이 0보다 같거나 작음 나간다.

# 현재 아이템에 포인트 1 해줌으로서, 지금 아이템을 선택 했을 절박도를 구한다

현재 아이템을 선택 할때 절박도 = findMaxHope ( 물건 리스트, 캐리어 용량, 현재 아이템 + 1) 


# 현재 아이템을 선택했을 절박도 ( 현재 아이템의 무게가, 남은 캐리어 용량보다 작아야된다 )

현재 아이템을 선택 할때 절박도  = findMaxHope ( 물건 리스트, 캐리어 용량 - 현재 아이템 무게 , 현재 아이템 + 1) 

        # 둘 중 큰 값 반환

return max ( 현재 아이템을 선택 할때 절박도, 현재 아이템을 선택 할때 절박도


}

 


식으로 간단히 표현해봤다. 

DP에서 가장 중요한 부분은 개인적인 의견으로 기저부분이라고 생각한다.. 

먼저 기저부분을 작성해준다. 


다음 논리적인 식을 적어주면된다. 현재 아이템을 선택 안 할때와 했을 때 절박도 중 최대값을 구해서 return해주면 절박도의 최대값을 구할 수 있다. 


But. 우리가 원하는 출력값에는 물건개수와 물건이름도 알아야한다. 

위의 식만 이용해선 물건개수와 물건이름을 알 수없다. 


아래 식을 추가해준다. 



getItemList ( 물건 리스트남은 캐리어 용량현재 아이템 , 아이템리스트 ){

      # 기저부분

      1. 현재 아이템이 마지막 아이템이면 나간다

      2. 남은 용량이 0보다 같거나 작음 나간다.

      

      # 두 값을 비교, 같다면 현재 아이템을 선택 안한 것이다. ( 현재 아이템을 선택 안 했기에, 절박도가 동일 ). 

      if ( findMaxHope ( 물건 리스트캐리어 용량현재 아이템 )  ==  findMaxHope ( 물건 리스트캐리어 용량현재 아이템 + 1)  )

      # 다음 포인트로 넘겨줌 

               getItemList ( 물건 리스트남은 캐리어 용량현재 아이템 + 1 , 아이템리스트 );

      else        

      # 현재 아이템까지 최대 절박도를 합친결과와 다음 아이템까지 최대 절박도를 합친 결과와 다르다면 현재 아이템은 선택된것이다. 

      # 선택 됐으니, 아이템 리스트에 추가하고, 무게를 빼서 다시 실행 

      ( 이 부분이 이해안간다면 , 위의 findMaxHope을 디버깅해가며 다시 본후 보면 이해가 빠를 것이다 ) 

              아이템리스트.add ( 현재 아이템 )

              getItemList ( 물건 리스트남은 캐리어 용량 - 현재 아이템 무게 현재 아이템 + 1 , 아이템리스트 );


}

 



이렇게 물건개수와 물건이름 또한 구할 수 있다. 


* 출처 : getItemList부분은 "알고리즘 문제해결 전략" 책을 참고하여 풀었습니다. 


 



쉽게 설명하기위해 한글로 적었는데 더 복잡한 느낌 ..

전체 코드를 보면 위에 그대로 코드로 표현하였다. 

추가된 부분 : cache 부분 추가 -- 이 부분이 없으면 timeout발생 

( dp를 이용할 때 memo기능을 이용해서 dp에서 실행된 결과는 cache처럼 저장하고 있다가 불러오면 시간단축을 할 수 있다 ) 



전체코드 

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;


public class Packing {


static int cache[][]  = new int[1001][100];

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int c = scanner.nextInt();

List<String> items = null;

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

int n = scanner.nextInt();

int w = scanner.nextInt();


List<Stuff> stuffs = new ArrayList<Stuff>();

items = new ArrayList<String>();

for ( int j = 0 ; j < n ; j ++  ) {

String name = scanner.next();

int weight = scanner.nextInt();

int hope = scanner.nextInt();

Stuff stuff = new Stuff(name, weight, hope);

stuffs.add(stuff);

}

for (int j = 0; j < 1001 ; j++) {

for(int k = 0; k < 100 ; k++) {

cache[j][k] = -1;

}

}

int point = 0;

int hope = findMaxHope(stuffs, w, point);;

getItemList(stuffs, w, point, items );

System.out.println(hope + " "+items.size());

for ( int j = 0 ; j < items.size() ; j++ ) {

System.out.println(items.get(j));

}


}

}

private static void getItemList(List<Stuff> stuffs, int w, int point, List<String> items )

{

if( point == stuffs.size() ) {

return;

}

if( w <= 0 ) {

return;

}

// 값이 다르다면  , 최대 절박도를 얻을 있다

    if (findMaxHope(stuffs, w, point) == findMaxHope(stuffs, w, point+1))

    getItemList(stuffs, w, point + 1, items);

    else

    {

    items.add(stuffs.get(point).getName());

    getItemList(stuffs, w - stuffs.get(point).getWeight() , point + 1, items);

    }

}

private static int findMaxHope(List<Stuff> stuffs, int w, int point) {

// 기저부분 

if( point == stuffs.size() ) {

return 0;

}

if( w <= 0 ) {

return 0;

}

if( cache[w][point] != -1) {

return cache[w][point];

}

// hope 절박도 

int hope = 0;

// 현재 아이템을 선택하지 않는 경우 ( 무게가 무거워 베낭에 담을 없을 )

hope = findMaxHope(stuffs, w, point+1);

// 현재 아이템을 선택할 경우 

if( w >= stuffs.get(point).getWeight() )

{

int rhope = ( findMaxHope(stuffs, w - stuffs.get(point).weight , point+1) ) + stuffs.get(point).hope ;

if( rhope > hope ) {

hope = rhope;

}

}

cache[w][point] = hope;

return hope;

}



static class Stuff {

String name;

int weight;

int hope;


public Stuff(String name, int weight, int hope) {

this.name = name;

this.weight = weight;

this.hope = hope;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public int getWeight() {

return weight;

}

public void setWeight(int weight) {

this.weight = weight;

}

public int getHope() {

return hope;

}

public void setHope(int hope) {

this.hope = hope;

}

}

}

 




'algolism' 카테고리의 다른 글

[카카오예선문제]캠핑풀이설명  (0) 2018.02.24
[알골스팟] XHAENEUNG문제  (0) 2018.02.16

+ Recent posts