알고리즘(3판)(FOUNDATION OF ALGORITHMS USING C++ PSEUDOCODE) 6장 예제코드 및 연습문제

소개글

알고리즘(3판)(FOUNDATION OF ALGORITHMS USING C++ PSEUDOCODE) 6장 예제코드 및 연습문제
*연습문제는 1번, 2번, 7번, 8번만 포함되어 있습니다. 착오 없으시길 바랍니다.

목차

1. 0 - 1 배낭채우기
2. 외판원 문제
3. 연습 문제

본문내용

문제: 무게와 이익이 주어진 n개의 아이템이 있다고 하자. 묵와 이익은 양의 정수이다. 게다가, 양의 정수 W도 주어진다.
무게의 합이 W가 넘지 못한다는 제약 하에서 ㅊ ᅟᅩᆼ 이익이 최대가 되는 아이템의 집합을 구하라
입력: 양의 정수 n과 W; 양의 정수의 배열 w와 p, 인덱스의 범위는 1부터 n까지이고, 각 배열은 p[i]/w[i] 값에 따라
큰 수부터 차례로 정렬되어 있다.
출력: 최적의 집합에 있는 이익의 합을 나타내는 정수 maxprofit

void knapsack3 (int n,
const int p[], const int w[],
int W,
int& maxprofit)
{
priority_queue_of_node PQ;
node u, v;
initialize(PQ);//PQ를 빈 대기열로 초기화
v.level = 0; v.profit = 0; v.weight =0;//v가 뿌리마디가 되게 초기화

maxprofit = 0;
v.bound = bound(v);
insert(PQ, v);
while (!empty(PQ)){//최고의 한계값을 가진 마디 제거
remove(PQ,v);
if (v.bound > maxprofit){//마디가 유망한지 검사
u.level = v.level + 1;
u.weight = v.weight + w[u.level];//u를 다음 아이템을 포함하는
u.profit = v.profit + p[u.level];//자식마디로 놓음
if(u.weight <= W && u.profit > maxrofit)
maxprofit = u.profit;
u.bound = bound(u);
if(u.bound > maxprofit)
insert(PQ, u);
u.weight = v.weight;//u를 다음 아이템을 포함하지 않는
u.profit = v.profit;//자식마디로 놓음

u.bound = bound(u);
if(u.bound > maxprofit)
insert(PQ,u);
)
)
)

참고 자료

없음