검색어 입력폼

[자바]자바 동적 계획을 이용한 배낭 문제

등록일 2006.05.07 한글파일한컴오피스 (hwp) | 6페이지 | 가격 2,000원

소개글

자바 동적 계획을 이용한 배낭 문제

컴파일 실행환경

자바

본문내용

<알고리즘 설명>

동적 계획이란? 정말로 필요할지 어떨지를 생각하지 않고 언젠가 필요해질 거 같은 작은 문제를 모두 풀어 테이블에 넣어두는 것

동적 계획을 이용하기 위한 조건
-문제들을 작은 문제들로 분할할 수 있어야 한다.
-분해된 각각의 작은 문제의 답을 조합하여 큰 문제를 해결할 수 있어야 한다.
-분할하여 얻어진 작은 문제들의 수가 너무 많으면 안된다.

배낭문제란? ‘N종류의 물건이 있고, 각각의 크기와 가격이 정해져 있을 때, 크기의 합계가 M이하가 되며 가격의 합계가 최대가 되는 물건들을 구하는 것. 즉, M만큼의 물건을 집어넣을 수 있는 배낭에 최대한 비싼 물건들을 집어넣는 것

구현 방법
-물건의 개수에 제한을 두지 않았다.
-물건의 크기는 정수로 한정하였다.
-우선 물건의 종류를 한 종류로 한정하여 문제를 풀어본다.
-물건의 종류를 한 종류를 더해가며 N개의 물건을 사용했을 때까지의 결과를 구해본다.
-주어진 배낭의 크기 M에 대해서가 아니라 0이상 M이하 모든 크기에 대하여 답을 구해 표로 정리한다.
-결과는 전체 합계와 마지막에 넣는 물건으로 나타난다.
-주어진 결과에서 먼저 배낭의 크기가 M일때 합계 와 마지막으로 들어가는 물건이 무엇인지 구한다.
-마지막 합계에서 마지막으로 들어가는 물건의 가격을 뺀다. 그리고 그 가격에서 마지막으로 들어가는 물건이 무엇인지 출력한다.
-위 과정을 합계가 0이 될때까지 분석한다.
다운로드 맨위로