[알고리즘] Knapsack Problem

*영*

개인인증 판매자스토어

최초 등록일: 2003.06.04
최종 저작일: 2003.06; 10페이지/ 한컴오피스; 가격 3,000원

다운로드

장바구니

상세정보
자료후기 (1)
자료문의 (0)
판매자정보

소개글

Knapsack Problem 구현 및 소스 입니다.

본문내용

◎ 배낭채우기 알고리즘

상태공간트리의 각노드에서 추정할수 있는 이득의 상한이 지금까지 조사된 해들중에서 가장 좋은 해의 값(이득의 하한)보다 같거나 작은면 퇴각한다.
같은 입력에 대해 0/1배낭 문제와 분할 가능 배낭 문제의 해를 비교해볼 때, 분할 가능 문제의 해는 0/1배낭문제의 해를 비해 항상 총 이득이 같거나 크는 것을 알 수 있다. 그래서, 분할가능 문제의 해는 0/1 배낭 문제의 해에 대한 상한으로 설정할 수 있다. 결과적으로 상태공간트리의 각 노드 x에서 이득의 상한 값은 bound를 다음과 같이 설정할 수 있다.

bound(x) = 현재까지 선택된 물건들의 이득의 합 +
남은 물건들과 남은 용량에 대한 분할 가능 배낭 문제의 해의 이득

상태공간트리의 각 노드 x를 방문할 시점 까지 조사된 최고 이득을 maxprofit이라고 설정하면,
x에 대한 한계 함수는 다음과 같이 설정할 수 있다.

◇ 노드 x에서 선택된 물건들의 무게의 합이 W를 초과하면 퇴각한다.
◇ 노드 x에서의 상한 bound가 maxprofit보다 같거나 작으면 퇴각한다.

◎ 주어진 아이템 데이터

참고 자료

없음

이 자료와 함께 구매한 자료

[알고리즘] 0/1 Knapsack Problem - Backtracking 3페이지
[컴퓨터 공학] 동적 계획법을 이용한 knapsack program 5페이지
[알고리즘] 분기한정, 0-1배낭채우기 6페이지
유전알고리즘과 활용 12페이지
0-1 Knapsack Problem 1페이지

자료후기(1)

주의사항

환불정책

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

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

이런 노하우도 있어요!더보기

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

분단탐색법 4페이지

, 배낭 문제(Knapsack problem), 버텍스 커버 문제(Vertex ... 분단탐색법은 외판원 문제(Traveling salesman problem) ... ) 등의 NP-hard Combinatorial Search Problem을
조합최적화 문제 4페이지

Problem) 7. ... - 작업공정 스케줄링(Job shop scheduling) - 배낭문제(Knapsack ... 대표적인 문제 - 순회 세일즈맨 문제(Traveling Salesman Problem
[알고리즘] Knapsack Problem 되추적 기법 구현 2페이지

]; return (bound > maxprofit); } } void knapsack ... + 1],NUMOFITEMS); include[i + 1]=false; knapsack ... = CAPA * 0.7 ; first=time((time_t*)0); knapsack
[알고리즘] Knapsack Problem 탐욕적방법과 동적계획법 3페이지

if (items[i].weight < capability) { dp_knapsack ... weight ... 10 } }; cout
[알고리즘] Knapsack Problem 분기한정기법 구현 4페이지

/* 알고리즘 knapsack (branch and bound) 배포판 knapsack ... 함수 원형에 예) void knapsack(int, const int[], ... 호출 예) knapsack(n, p, w, W, maxprofit);
[알고리즘]배낭문제(0/1Knapsack Problem) 7페이지

배낭 알고리즘을 C코드로 구현한 소스와 보고서이다. 1.Knapsack ... 0-1 Knapsack Problem)라 부른다. 2.함수 설명 ... problem 이란?
[공학]Knapsack(배낭) Problem 프로그램 - Greedy 알고리즘 2페이지

목적 - Knapsack Problem 을 해결하기위한 Greedy 알고리즘에 ... 가장 높은 물건을 배낭에 차례대로 넣는다.void knapsack(float ... 4, 1}; // 물건의 무게//-- main 함수void main(){knapsack
[알고리즘] 0/1 Knapsack Problem - Backtracking 3페이지

이 알고리즘은 자바로 구현되었습니다.0/1Knapsack Problem 을 ... Backtracking 알고리즘을 사용하여 작성하였습니다.입력파일은 압축파일에
[알고리즘]0-1 knapsack problem의 branch and bound algorithm을 구현한 프로그램 2페이지

각 물건의 종류가 얼마든지 많이 공급되는 0-1 knapsack problem의 ... 때마다 그 노드의 bound 값을 출력한다.branch-and-bound 알고리즘이 ... 정수이다.출력의 format은 아래와 같이 해야 한다:branch-and-bound 알고리즘의
[알고리즘]0-1 Dynamic Knapsack Problem (Java) 0페이지

.....1■ Program source .............11. knapsack_operter.java2
[알고리즘] 0/1 Knapsack Problem - Branch And Bound 4페이지

이 알고리즘은 자바로 구현하였습니다.0/1Knapsack Problem 을 ... Branch And Bound 알고리즘을 사용하여 작성하였습니다.입력파일은
공장설계및실습 과제8.Maximum Flow Problem 40페이지

Knapsack Problem 10 1. Introduction 2. ... each stock piece 0.00 Stock cost = 310.00 알고리즘을 ... Trim Problem: Cutting Stock 23 1.
0-1 Knapsack Problem을 c언어로 구현한 보고서 13페이지

0-1 Knapsack Problem ▣ 문제 분석 ▶ 0-1 Knapsack ... 를 큰 순서로 나열하기 위한 정렬 알고리즘은 본인의 선택에 의해 아무거나 ... x2, x3, x4) = (1, 1, 0, 0) ▣ 문제 풀이방법 및 알고리즘
Dynamic Programming 기법을 이용한 Knapsack Problem 해결 0페이지

알고리즘중에서 Dynamic Probramming 기법을 이용하여 Knapsack ... problem 을 해결하는 소스입니다. ... C++ 로 작성되었으며 knapsack 제한조건으로 무게만 적용하였을 때,
0-1 knapsack 문제에 대한 Dynamic Programming과 Backtracking과 Branch-and-Bound 알고리즘의 실행시간 비교(소스와 결과캡쳐 포함) 15페이지

비교 ● 0-1 배낭채우기(0-1 Knapsack Problem) 0-1 ... 1 : Algorithm 5.7을 이용하여 0-1 Knapsack Problem을 ... Dynamic Programming 알고리즘을 적용한 0-1 Knapsack
Depth first knapsack Algorithm 5페이지

Problem ... problem algorithm. //7.December.2007 #include ... ***********\n"); putchar('\n'); printf("Problem