김동건/eatRawLife

김동건/eatRawLife

열심히 해보려고요.

배낭 문제(knap sack)

5 minute read

Published:

익숙한 캐릭터가 나오는 문제를 풀다가, 조합에 관련된 문제인건 알았으나 복잡도는 너무 크고, 그렇다고 해결책도 보이지 않았던 문제가 있었다.

[GOLD 3] 시로코와 은행털기

결국 해결하지 못하고, 문제의 분류를 보고 확인한 키워드는 아래와 같았다.

  • dp
  • 배낭 문제

배낭 문제라는 단어를 처음 보았다. 그러나 DP를 이용한 유명한 문제라고 한다. 이에대해 정리해 보겠다.

배낭 문제(背囊 問題, knapsack problem)는 조합 최적화 문제의 일종이다. 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 ‘가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제’ 이다.

*출처 킹무위키

대충 말하면 가장 좋은 조합을, 빠르게 찾는것을 말하는 것이다.

분할 가능한 배낭 문제

문제

코드트리 : 쪼개어 배낭 채우기

만약 도둑이 물건을 훔치려 한다 가정하자, 그리고 도둑은 망치와 드라이버를 가져와 보석이 몇 kg 단위로만 취급되던 원하는 크기만큼 쪼개서 들고 갈 수 있다.

따라서 무게당 가격이 가장 비싼걸로만 골라가도 가방에 담을 수 없는 문제는 일어나지 않는다

풀이

그리디 알고리즘을 이용한다.

무게당 가격이 가장 비싼 보석부터 차례로 가방에 집어넣고, 가방 크기보다 보석이 크다면 쪼개서 들고간다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

//https://en.cppreference.com/w/cpp/language/operator_arithmetic.html 문서 읽기 해보기

/*
typedef struct {
  int w;
  int v;
  double rv;
} back; 
 */
//스트럭트를 쓸 수 도 있지만, 3개 이상의 인자를 가진, 튜플을 이용할 수도 있다.
//원소 접근 > std::get<인덱스>(튜플);
//튜플 생성 > make_tuple(원소.....);

//typedef 대해서도 알아야.

typedef std::tuple<int, int, double> back;
int N, M;
std::vector<back> v;

bool compare(back b1, back b2){
  return std::get<2>(b1) < std::get<2>(b2);
}

int main() {
    std::cin >> N >> M;

    for (int i = 0; i < N; i++) {
        int temp1;
        int temp2;
        std::cin >> temp1 >> temp2;
        back temp = std::make_tuple(temp1, temp2, (temp2 /(double)temp1)); // 보통 double 만들기 하려면 뒤에 거에 double 붙이더라
        v.push_back(temp);
    }
    sort(v.begin(),v.end(), compare);//알고리즘의 sort 메소드는 어떻게 사용할 것인가, std:: 왜 안붙여도 되는가, compare 이없다면 어디를 따라가는가


    double sum= 0;
    int limit = M;
    for(int i = v.size()-1; i>= 0; i--) {
      if(limit >= std::get<0>(v[i])){
        sum += std::get<1>(v[i]);
        limit -= std::get<0>(v[i]);
      } else {
        sum += limit * std::get<2>(v[i]);
        break; //알고리즘 풀때 집중! 뭐하나 빼먹지 않게.
      }
      
    }
   

    //printf("%.3f", sum);
    std::cout << std::fixed;
    std::cout.precision(3);
    std::cout << sum;




    return 0;
    //이와중에 bag를 back이라 썼네.. 이런;;
}

피드백 - 몰랐던 것, 실수한 것

문제 발상 자체는 정말 쉬웠다. 하지만 구현에서의 이전에 없던 몇가지 이슈가 발생했다.

  • 보석은 무게, 가치 ,무게당 가치 세가지 값을 가진다. 정렬 등의 편의를 위해서 이 셋을 묶어야한다. 어떻게 하지? -> 튜플을 이용한다.
  • 정렬은 어떻게 하는가? -> <algorithm>의 sort 이용
  • int/int 시 실수. 연산자의 시멘틱스는 어디서 파악해야하는가..
  • 출력시 부동소수점 자료형 소수점 자리 고정은 어떻게 하는가

피드백 - 타인 코드 참조

  • 여러 값들을 이용하는 객체 같은경우, 코딩테스트의 경우는 간단하게 튜플을 이용한다.
  • std::get으로 튜플의 값들을 가져올 수 있지만 ocaml에서 타입 매칭 하듯 std.tie(받을 원소…)를 이용해서도 원소들을 받을 수 있다.

0/1 배낭문제

문제

[GOLD 5] 평범한 배낭

이번엔 가방에 가능한 높은가치의 물건을 무게 제한을 넘지 않게 넣되, 물건을 쪼개서 넣을 수는 없다.

생각난 짤

이렇게 말이다…

따라서 무게당 가치가 가장 높은 물건부터 차례로 가방에 집어넣으면, 가방에 안들어 갈 수 있다.

해결

DP를 이용한다.

DP에 대한 몰이해에 의해서 어느정도 DP를 따라하긴 했으나 잘못 풀었다. 올바른 풀이를 이용하여 다시 풀어 보겠다.

참고한 영상

  1. 문제: 물건을 골라서 무게합이 M일때 최대의 가치가 되도록 하기

  2. Subproblem :
    dp[i,w] = 1~i까지 물건의 포함여부를 결정했을며 그 무게가 w ‘이하’일때 가치의 최대값. (이하가 없다면 복잡해진다. 왜일지 한번 생각해보자.),
    이때 정답 : dpN,M

  3. recurrence relation : 물건을 넣을지 말지 하나씩 체크해나간다고 할때, 담을 수 있는 물건이라면 dp[i,w] 가 될 수 있는 경우는 i번째 물건을 가져오거나, i번째 물건을 스킵하거나 둘중하나. 이때 가치의 합이 큰녀석만 선택하면 된다.
    따라서 i번째 물건을 선택하지 않은 subproblem, 무게가 w이하인 subproblem이 필요 > 두가지 변수, 2차원의 메모이제이션 테이블.

    if 허용 무게 초과:
  dp[i,w] = dp[i-1,w]
else
  dp[i,w] = max((dp[i-1, w-<i번째 물건의 무게>] + <i번째 물건 가치>) ,dp[i-1,w])

    베이스케이스 : dp[0,0~m] = 0
    아직 아무물건도 고려하지 않음.
    구현시 첫 인덱스를 첫 물건 삽입여부를 고려하는 방법도 있었는데 구현이 어려웠다. (삽입여부 if 문으로 해서 꽉채워주고, 이후는 기존과 동일한 식. 이게 무슨 생고생이야.)

디펜던시 : 메모이제이션 테이블에서 바로 윗칸, 좌측 윗칸이 필요함 > 좌->우 후 위 -> 아래로 진행.
(논리 진행상 위 아래 진행이 더 맞지만, 그러면 계속 배열에 접근해야해서 비효율적.)

  1. 시간 복잡도 :
    베이스 케이스 추가 : O(N)
    나머지 한칸당 계산시 상수시간. = 총 O(NM)

코드

#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>


typedef std::tuple<int, int> stuff;
int N;
int K;
std::vector<stuff> l;
//1based, 물건 인덱스 0번은 아무것도 더하지 않은 케이스 위해, 무게 인덱스 0번은 입력이 1based로 들어와서.
int weigh[101][100001];

int main() {
  std::cin >> N >> K;
  for(int i = 0 ; i< N; i++) {
    int one, two;
    std::cin >> one >> two;
    stuff temp = std::make_tuple(one,two);
    l.push_back(temp);
  }

  for(int i = 1; i<=N; i++ ){
    int w, v;
    std::tie(w, v) = l.at(i-1);//벡터는 어쩔수 없이 0based임을 고려한 i-1.
    for(int limit = 1; limit <= K; limit++) {
      if(w> limit)
      weigh[i][limit] = weigh[i-1][limit];
      else{
        int plus,stay;
        stay = weigh[i-1][limit];
        plus = weigh[i-1][limit-w] + v;

        if(stay >plus){
          weigh[i][limit] = stay;
        }
        else
        weigh[i][limit] = plus;
      }
    }
  }
  
  std::cout << weigh[N][K];
}

구현 자체는 굉장히 할만 했다.

  • 구현 편의를 위해 고려한 물건이 없는 케이스 두기

느낀점

  • 모르겠으면 적당히 하고 찾아보자. 계속 전 구우니 시간은 날아가고, 올바른 풀이 부족한점 확인할 시간은 없다. 문제풀이 양치기보다 타인의 답안 확인해서 부족한부분 채워나가는게 더 중요한것 같다.