[알고리즘-C++] 분기한정(Branch & Bound)를 이용한 0-1 배낭 채우기

2022. 5. 28. 23:11· Skils/Algorithm
목차
  1. 구현
되추적 알고리즘을 이용한 0-1 배낭 채우기를 앞에서 해보았다.

 

이번에는 분기한정을 이용한 0-1 배낭 채우기를 해보겠다. 되추적 알고리즘과 어떤 차이가 있는지를 중점으로 보면 될 것이다.

 

-앞선 문제와 동일하게

n= 보석의 개수

W= 배낭의 용량

 

n=4, W=13

p(profit)=[40,30,50,10], w(weight)=[2,5,10,5], p/w(단위 무게별 이익)=[20,6,5,2]

 

1. 앞선 0-1 배낭 채우기 문제와 같이 무게별 이익이 큰 순서대로 재 정렬한다.

2. 되추적 알고리즘과 상태 공간 트리를 구성한다.

3. 트리는 (profit, totweight, bound)로 이루어진다.

  • profit은 내가 가방에 담은 이익
  • totweight은 내가 가방에 담은 무게
  • bound는 내가 탐색한 부분에서 최대로 담을 수 있는 한계값

4. 가지치기 조건은 되추적 알고리즘과 동일하다.

※되추적 알고리즘과 다른 점

  1. (1,1)과 (1,2)를 비교해서 bound값이 가장 크면서 유망하고, 확장하지 않은 마디인 (1,1)의 자식들을 탐색한다.
  2. (2,1), (2,2) 중에서 유망하고 확장하지 않은 마디인 (2,1)를 방문
  3. (3,1)은 가지치기 조건에 의해서 방문 x (3,2)를 방문함.
  4. (2,2)와 (3,2) 중에서 유망하고 확장하지 않은 마디인 (2,2)를 방문함.
  5. (3,3)를 방문. 가지치기 조건에 걸리지 않아서 방문함.
  6. (3,4)를 방문하는데 이미 (3,3)에서 maxprofit이 90으로 초기화되어서 (3,4)의 bound값이 maxprofit보다 작기 때문에 방문 x
  7. (3,3)을 방문함.
  8. (4,1)은 무게가 17, W를 넘기 때문에 방문 x
  9. (4,2)는 한계값이 maxprofit보다 같기 때문에 유망하지 않다고 결정, 그 뒤에 자식 노드들은 이미 maxprofit을 넘을 수 없는 구조기 때문에 확장을 하지 않는다.

--> 결과 (3,3)이 가장 유망한 방문이다.

구현

1. 구조체 선언 

typedef struct node *node_p;
typedef struct node
{
int level;
int weight;
int profit;
float bound;
} nodetype;

2. 우선순위 대기열(priority queue)을 사용한다.

  • 정렬 조건은 bound값이 큰 순서대로 넣어준다.
  • 이유는 bound값이 가장 큰 게 유망하기 때문에 그 유망한 노드를 찾기 위해서 pq.top을 사용해야 함.

3. Bound계산

  • bound값은 내가 현 상황에서 가장 큰 이익을 계산해줌.(실제로는 보석을 분할할수는 없지만 분할할수있다고 가정하고 계산)
float bound(node_p u)
{
int j, k, totweight;
float result;
if (u->weight >= W) //그때 방문했던 노드의 무게 합이 W보다 크다면 잘못된 방문임을 뜻함.
return 0;
else
{
result = u->profit;
j = u->level + 1;
totweight = u->weight;
while (j <= N && totweight + Weight[j] <= W)
{
totweight += Weight[j];
result += profit[j];
j++;
}
k = j;
if (k <= N)
result += (W - totweight) * ((float)profit[k] / Weight[k]);
return result;
}
}

bo

4. 배낭 채우기 함수

void knapsack6()
{
priority_queue<node_p, vector<node_p>, compare> pq; // bound값으로 내림차순 정렬해서 넣어줫음.
node_p u, v;
u = (node_p)malloc(sizeof(nodetype) * N);
v = (node_p)malloc(sizeof(nodetype) * N);
maxprofit = 0;
v = create_node();
v->level = 0;
v->profit = 0;
v->weight = 0;
v->bound = bound(v);
print_node(v);
pq.push(v);
while (!pq.empty())
{
v = pq.top();
pq.pop();
// print_node(v);
if (v->bound > maxprofit)
{
//가방에 보석을 담은경우
u = create_node();
u->level = v->level + 1;
u->weight = v->weight + Weight[v->level + 1];
u->profit = v->profit + profit[v->level + 1];
u->bound = bound(u);
print_node(u);
if (u->weight <= W && u->profit > maxprofit) //내가 다음 노드로 진행햇는데 그때의 무게가 W보다 작거나 같아야함.
{
maxprofit = u->profit; //그때의 이익이 만약 maxprofit보다 크다면 최신화시켜줌.
}
if (u->bound > maxprofit)
{
pq.push(u); //내가 설정한 바운드값보다 maxprofit이 크다면 pq에 푸쉬해줌.
}
//가방에 보석을 담지 않는 경우.
u = create_node();
u->level = v->level + 1;
u->weight = v->weight;
u->profit = v->profit;
u->bound = bound(u);
print_node(u);
if (u->bound > maxprofit)
{
pq.push(u);
}
}
}
}

코드

/*
branch&Bound를 이용한 0-1 Knapsack problem
무게대비 이득을 내림차순으로 정렬
유망한것부터 탐색함.
유망한것은? Bound값이 높은것.
Prority queue를 이용함. Bound값을 기준으로 내림차순 정렬
내가 탐색한 노드의 바운드 값이 maprofit보다 낮다면 굳이 탐색할 필요가없음.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct node *node_p;
typedef struct node
{
int level;
int weight;
int profit;
float bound;
} nodetype;
struct compare
{
bool operator()(node_p a, node_p b)
{
return a->bound < b->bound;
}
};
int N, W;
vector<int> profit;
vector<int> Weight;
int maxprofit;
void knapsack6();
float bound(node_p u);
node_p create_node();
void print_node(node_p u);
int main()
{
cin >> N >> W;
Weight.resize(N + 1);
profit.resize(N + 1);
for (int i = 1; i <= N; i++)
{
int w;
cin >> w;
Weight[i] = w;
}
for (int j = 1; j <= N; j++)
{
int a;
cin >> a;
profit[j] = a;
}
// profit/weight 큰 것으로 정렬
for (int i = 1; i <= N; i++)
{
for (int j = i + 1; j <= N; j++)
{
if (profit[i] / Weight[i] < profit[j] / Weight[j]) // 앞에게 더 크다면 나둠
{
swap(profit[i], profit[j]);
swap(Weight[i], Weight[j]);
}
}
}
knapsack6();
cout << maxprofit;
}
void knapsack6()
{
priority_queue<node_p, vector<node_p>, compare> pq; // bound값으로 내림차순 정렬해서 넣어줫음.
node_p u, v;
u = (node_p)malloc(sizeof(nodetype) * N);
v = (node_p)malloc(sizeof(nodetype) * N);
maxprofit = 0;
v = create_node(); //v는 초기 root node임.
v->level = 0;
v->profit = 0;
v->weight = 0;
v->bound = bound(v);
print_node(v);
pq.push(v);
while (!pq.empty())
{
v = pq.top();
pq.pop();
// print_node(v);
//bound는 이익의 상한선.
if (v->bound > maxprofit) //만약 bound가 maxprofit보다 작다면 밑에 것은 굳이 탐색할 필요가 없음,.
{
//가방에 보석을 담은경우
u = create_node();
u->level = v->level + 1;
u->weight = v->weight + Weight[v->level + 1];
u->profit = v->profit + profit[v->level + 1];
u->bound = bound(u);
print_node(u);
//보석을 담았는제 가방 무게인 W를 초과해선 안되고 담은 이익이 maxprofit 보다 크다면 초기화시켜줌.
if (u->weight <= W && u->profit > maxprofit)
{
maxprofit = u->profit;
}
if (u->bound > maxprofit) //bound값이 maxprofit보다 작다면 유망하지않음.
{
pq.push(u);
}
//가방에 보석을 담지 않는 경우.
u = create_node();
u->level = v->level + 1;
u->weight = v->weight;
u->profit = v->profit;
u->bound = bound(u);
print_node(u);
if (u->bound > maxprofit) // bound값이 maxprofit보다 작다면 유망하지않음.
{
pq.push(u);
}
}
}
}
node_p create_node()
{
node_p temp;
temp = (node_p)malloc(sizeof(nodetype) * N);
return temp;
}
float bound(node_p u)
{
int j, k, totweight;
float result;
if (u->weight >= W) //그때 방문했던 노드의 무게 합이 W보다 크다면 잘못된 방문임을 뜻함.
return 0;
else
{
result = u->profit;
j = u->level + 1;
totweight = u->weight; //현재무게
while (j <= N && totweight + Weight[j] <= W) //보석의 끝까지 탐색하며 현재무게가 제한무게가 될때까지 더해줌.
{
totweight += Weight[j];
result += profit[j];
j++;
}
k = j;
if (k <= N) //만약 무게를 초과햇는데 가방을 끝까지 돌지못했다면 쪼개서 넣어줌.
result += (W - totweight) * ((float)profit[k] / Weight[k]);
return result;
}
}
void print_node(node_p u)
{
cout << u->level << " " << u->weight << " " << u->profit << " " << u->bound << endl;
}

💡정리

  • bound와 totweight의 개념을 잘 이해해야함.
    • bound는 내가 기대할수있는 이익의 상한선. 이것보다 더 큰 이익은 그 경로에서 나올수가없다.
      • bound는 내가 현재 담을 수 있는 최대의 이익을 구하면 됨.(분할가능)
      • 따라서 bound값이 maxprofit보다 작거나 같다면 유망하지 않으므로 탐색x
    • totweight는 현재 내가 담은 무게.
      • W보다 작거나 같아야함.
  • node 탐색 순서는 BFS를 따르지만 BFS + Branch & Bound를 이용함.
    • 여기서 탐색 우선순위는 Bound값이 높은 노드다.
    • 당연히 Bound값이 높은 노드들에서 최적값을 찾을 확률이 높다.

 

 

느낀 점

배낭 문제를 워낙 많이 풀다 보니까 분기 한정이라는 새로운 기법(?)으로 풀어도 이해하기 쉬웠다.
분기 한정과 되추적 알고리즘의 디테일한 차이를 아는 것이 이번 단원의 중요한 목표인 것 같다.
저작자표시 (새창열림)

'Skils > Algorithm' 카테고리의 다른 글

[알고리즘-C++] - 외판원 순회 문제(Branch & Bound)  (1) 2022.05.31
[알고리즘-C++] 외판원 순회 문제(Dynamic Programming)  (0) 2022.05.29
[C++] 알고리즘 이론 - Branch & Bound (분기 한정)  (0) 2022.05.28
[C++]알고리즘 - 기사의 여행 문제와 해밀턴 경로  (0) 2022.05.28
알고리즘[C++] 0-1 knapsack problem with Backtracking(백트래킹)  (0) 2022.05.23
  1. 구현
'Skils/Algorithm' 카테고리의 다른 글
  • [알고리즘-C++] - 외판원 순회 문제(Branch & Bound)
  • [알고리즘-C++] 외판원 순회 문제(Dynamic Programming)
  • [C++] 알고리즘 이론 - Branch & Bound (분기 한정)
  • [C++]알고리즘 - 기사의 여행 문제와 해밀턴 경로
재한
재한
안녕하세요 💻
재한
짜이한
전체
오늘
어제
  • 분류 전체보기 (502)
    • Skils (116)
      • Android (50)
      • C++ (5)
      • Kotlin (36)
      • Algorithm (24)
      • Server (1)
    • CodingTest (228)
      • Programmers (45)
      • Baekjoon (183)
    • Experience (8)
      • 후기(코딩테스트,프로그램,프로젝트) (8)
    • Computer Science (70)
      • Design Pattern (2)
      • OOP (2)
      • Computer Architecture (14)
      • OS (2)
      • Software Engineering (3)
      • DataBase (8)
      • Network (39)
    • 학교 (75)
      • R프로그래밍 (26)
      • 회계와 사회생활 (17)
      • 컴퓨터학개론 (20)
      • it기술경영개론 (12)

블로그 메뉴

  • 홈
  • 태그
  • 카테고리
  • 글쓰기
  • 설정

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
재한
[알고리즘-C++] 분기한정(Branch & Bound)를 이용한 0-1 배낭 채우기
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.