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

Dev
개인인증판매자스토어
최초 등록일
2016.09.15
최종 저작일
2015.06
19페이지/한글파일 한컴오피스
가격 1,000원 할인쿠폰받기
다운로드
장바구니
퀴즈OX 이벤트

소개글

알고리즘(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);
)
)
)

참고 자료

없음

이 자료와 함께 구매한 자료

자료후기(2)

Dev
판매자 유형Gold개인인증

주의사항

저작권 자료의 정보 및 내용의 진실성에 대하여 해피캠퍼스는 보증하지 않으며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
자료 및 게시물 내용의 불법적 이용, 무단 전재∙배포는 금지되어 있습니다.
저작권침해, 명예훼손 등 분쟁 요소 발견 시 고객센터의 저작권침해 신고센터를 이용해 주시기 바랍니다.
환불정책

해피캠퍼스는 구매자와 판매자 모두가 만족하는 서비스가 되도록 노력하고 있으며, 아래의 4가지 자료환불 조건을 꼭 확인해주시기 바랍니다.

파일오류 중복자료 저작권 없음 설명과 실제 내용 불일치
파일의 다운로드가 제대로 되지 않거나 파일형식에 맞는 프로그램으로 정상 작동하지 않는 경우 다른 자료와 70% 이상 내용이 일치하는 경우 (중복임을 확인할 수 있는 근거 필요함) 인터넷의 다른 사이트, 연구기관, 학교, 서적 등의 자료를 도용한 경우 자료의 설명과 실제 자료의 내용이 일치하지 않는 경우

찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

우수 콘텐츠 서비스 품질인증 획득
최근 본 자료더보기
알고리즘(3판)(FOUNDATION OF ALGORITHMS USING C++ PSEUDOCODE) 6장 예제코드 및 연습문제 무료자료보기