Search

'책상 위 컴퓨터/Data Structure & Algorithm'에 해당되는 글 3건

  1. 2016.04.18 [Algorithm] 배낭채우기2(1278) - jungol
  2. 2016.04.13 [Algorithm] 배낭채우기(1077) - jungol
  3. 2008.05.06 1. SelectionSort

[Algorithm] 배낭채우기2(1278) - jungol

책상 위 컴퓨터/Data Structure & Algorithm 2016.04.18 23:46 Posted by 잡학 저장소 잡학저장소


Click 문제 바로 가기 : JUNGOL 






문제 : 배낭채우기2 (1278)



제한시간 

 1Sec 

메모리제한

 64mb 



입력 형식 : 



입력의 첫 줄은 보석의 개수 N(1≤N≤1,000)과 배낭의 용량 W(1≤W≤10,000)가 주어진다.

둘째 줄부터 N+1줄에는 각 보석의 무게 Wi(1≤Wi≤W)와 값어치 Pi가 주어진다. (단, 보석은 각 종류별로 1개씩이다.)



출력 형식 : 



출력은 보석의 무게와 값어치가 주어질 때 총 무게가 W를 넘지 않으면서 보석의 총 값어치가 최대가 되는 최대값을 출력한다.



입력 예 

 출력 예

 4 16

90 

 2 40

 

 5 30

 

 10 50

 

 5 10

 







[Algorithm] 배낭채우기(1077) - jungol

책상 위 컴퓨터/Data Structure & Algorithm 2016.04.13 22:33 Posted by 잡학 저장소 잡학저장소



Clink 문제 바로 가기 : JUNGOL 






문제 : 배낭채우기 (1077) 


 제한시간

 1 Sec

 메모리제한

 64 mb 

 

 



입력 형식 : 



첫 줄은 보석의 가지 수 N(1≤N≤1,000)과 배낭의 용량 W(1≤W≤10,000)가 주어진다. 


둘째 줄부터 N+1줄에는 각 보석의 무게 Wi(1≤Wi≤W)와 값어치 Pi가 주어진다. (단, 각각의 보석의 개수는 무제한으로 가정한다.)



출력 형식 : 



보석의 무게와 값어치가 주어질 때 총 무게가 W를 넘지 않으면서, 보석의 총 값어치가 최대가 되는 최대값을 출력한다.



 입력 예

 

출력 예 

 4 14

 

 300

 2 40

 

 

 5 110

 

 

 3 50

 

 

 

 

 






참고 이론 : 배낭문제 (출처 : 위키피디아) 


배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다.


간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.


이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다.


이 문제는 쪼갤 수 있는 경우에는 그리디 알고리즘으로 다항 시간에, 쪼갤 수 없는 경우에는 동적계획법(Dynamic Programming)등으로 의사 다항 시간에 풀 수 있다. 단, 쪼갤 수 없는 경우는 NP-완전이기 때문에 알려진 다항 시간 알고리즘은 없고, FPTAS만 존재한다. 배낭 문제에 대한 FPTAS는 오스카 이바라와 김철언이 1975년에 개발하였다.[1]







개인적 풀이 : 




0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 0 0 - - - - - - - - - - - - -
2 0 0 40 - - - - - - - - - - - -
3 0 0 40 50 - - - - - - - - - - -
4 0 0 40 50 80 - - - - - - - - - -
5 0 0 40 50 80 110 - - - - - - - - -
6 0 0 40 50 80 110 120 - - - - - - - -
7 0 0 40 50 80 110 120 150 - - - - - - -
8 0 0 40 50 80 110 120 150 160 - - - - - -
9 0 0 40 50 80 110 120 150 160 190 - - - - -
10 0 0 40 50 80 110 120 150 160 190 220 - - - -
11 0 0 40 50 80 110 120 150 160 190 220 230 - - -
12 0 0 40 50 80 110 120 150 160 190 220 230 260 - -
13 0 0 40 50 80 110 120 150 160 190 220 230 260 270 -
14 0 0 40 50 80 110 120 150 160 190 220 230 260 270 300


전략  : DP 에서는 일정한 패턴의 값은 미리 Table 화 하여 값을 가지고 있는다. 

위의 Table 에서 보듯이 1 -> 2 -> 3 -> 4 -> 5 ... 순으로 마지막 14까지 값을 구한다. 

노란색 부분은 값의 최대(노란 색 부분이 꼭 구해진 값이라는 보장은 없다) 값으로 설정된 구간을 말함 

최종 무게가 14 를 가지기 위한 최대 값은 "300" 이다. 



Pseudo Open



1. SelectionSort

책상 위 컴퓨터/Data Structure & Algorithm 2008.05.06 08:39 Posted by 잡학 저장소 잡학저장소

/*
SelectionSort : sort contiguous list by the selection sort method.
Pre : The contiguous list list has been created. Each entry of list contains a key.
Post : The entries of list have been rearranged so that the keys in all the entries are sorted into nondecreasing order.
Uses : MaxKey, Swap
*/

void SelectionSort( List * list ){
   Position current; /* position of place being correctly filled */
   Position max; /* position of largest remaining key */
   for ( current = list -> count - 1; current > 0; current-- ){
      max = MaxKey ( 0, current, list );
      Swap ( max, current, list );
   }
}


/*
MaxKey : find the position of the largest key in the sublist.
Pre : The contiguous list list has been created. low and high are valid positions in list.
Post : The position of the entry between low and high with the largest key is returned
*/

Position MaxKey( Position low, Position high, List * list ){
   Position largest; /* position of largest key so far */
   Position current; /* index for the contigous list */
   largest = low;
   for( current = low + 1; current <= high; current++ )
      if( LT( list->entry[ largest ].key, list->entry[ current ].key ) )
         largest = current; 

   return largest;
}


/*
Swap : swap two entries in the contiguos list.
Pre : The contiguos list list has been created. low and high are valied positions in list.
Post : The entry at position low is swapped with the entry at position high
*/

void Swap( Position low, Position high, List * list ){
   ListEntry temp = list->entry[ low ];
   list->entry[ low ] = list->entry[ high ];
   list->entry[ high ] = temp;
}


/* 발췌 ---------------- Data Structures And Program Design in C */

public class Test {
   public static void main(String [] args){
      int [] array = { 7, 2, 3, 1, 5, 6 };
      SelectionSort selectionSort = new SelectionSort(array);
      selectionSort.runSort();
      selectionSort.print();
   }
}

class SelectionSort{
 
   int [] array;
 
   public SelectionSort(int [] array){
      this.array = array;
   }
 
   public void runSort(){
      int current;
      int max;
      for( current = array.length-1; current > 0 ; current-- ){
         max = this.getMaxKey( 0, current , array);
         runSwap( max, current, array );
      }
   }
 
   public int print(){
      int length = this.array.length;
      for( int count = 0; count < length; count++ )
         System.out.println(array[count]);
      return length;
   }
 
   private int getMaxKey( int low, int high, int [] array ){
 
      int largest;
      int current;
      largest = low;
 
      for( current = low+1 ; current <= high; current++ ){
        if( array[ largest ] <= array[ current ] ){
           largest = current;
        }
     }
 
    return largest;
 }
 
   private void runSwap( int low, int high, int [] array ){
      int temp = array[ high ];
      array[ high ] = array[ low ];
      array[ low ] = temp;
   }
}