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

소개

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

컴파일 실행환경

자바

본문내용

<알고리즘 설명>

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

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

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

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

참고자료

· 없음