• LF몰 이벤트
  • 파일시티 이벤트
  • 캠퍼스북
  • 서울좀비 이벤트
  • 탑툰 이벤트
  • 닥터피엘 이벤트
  • 아이템베이 이벤트
  • 아이템매니아 이벤트

0-1 Knapsack Problem을 c언어로 구현한 보고서

*하*
개인인증판매자스토어
최초 등록일
2012.12.06
최종 저작일
2012.07
13페이지/한글파일 한컴오피스
가격 5,000원 할인쿠폰받기
다운로드
장바구니

소개글

0-1 Knapsack Problem을 c언어로 구현한 보고서 입니다.
구현 및 분석까지 완벽한 보고서이며, 코드는 보고서에 포함되어 있습니다.

목차

▣ 문제 분석
▣ 문제 풀이방법 및 알고리즘
▣ program
▣ 입출력의 예 및 출력결과
▣ 결과 분석 및 토의

본문내용

▣ 결과 분석 및 토의
1. Knapsack Problem
배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최대 값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.
이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다.

이 문제는 쪼갤 수 있는 경우에는 greedy 알고리즘으로 다항 시간에, 쪼갤 수 없는 경우에는 동적계획법(Dynamic Programing)등으로 의사 다항 시간에 풀 수 있다. 단, 쪼갤 수 없는 경우는 NP-완전이기 때문에 알려진 다항 시간 알고리즘은 없고, FPTAS만 존재한다. 배낭 문제에 대한 FPTAS는 오스카 이바라와 김철언이 1975년에 개발하였다.

2. backtracking

backtracking의 방법은 검색이 완전히 끝나기 전에는 해답을 알 수 없으므로 검색하는 과정 동안 항상 그 때까지 찾은 최적의 해를 기억해야한다.

노드가 레벨 i에 있고, 레벨 k에 있는 노드에서 총 무게가 w를 넘었을 때의 식은 다음과 같다.

참고 자료

없음
*하*
판매자 유형Bronze개인인증

주의사항

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

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

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

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

최근 본 자료더보기
  • 프레시홍 - 전복
탑툰 이벤트
0-1 Knapsack Problem을 c언어로 구현한 보고서
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업