>  기사  >  Java  >  Java에서 배낭 알고리즘을 구현하는 방법에 대한 예제 분석

Java에서 배낭 알고리즘을 구현하는 방법에 대한 예제 분석

黄舟
黄舟원래의
2017-08-23 10:46:541756검색

이 글에서는 주로 배낭 알고리즘(0-1 배낭 문제)을 Java로 구현하는 방법에 대한 간략한 논의를 소개합니다. 편집자는 꽤 좋다고 생각하므로 이제 공유하고 참고용으로 제공하겠습니다. 편집자를 따라가서 살펴보겠습니다

0-1 배낭 문제

배낭 문제는 조합 최적화의 NP 완전 문제입니다. 문제는 다음과 같이 설명할 수 있습니다. 품목 세트가 주어지면 각 품목에는 고유한 무게와 가격이 있습니다. 제한된 총 무게 내에서 품목의 총 가격이 가장 높도록 어떻게 선택합니까? 문제의 이름은 주어진 배낭에 넣을 가장 적절한 품목을 선택하는 방법에서 비롯됩니다.

가장 기본적인 백팩 문제입니다. 특징은 종류별로 아이템이 하나씩만 있고, 넣을지 말지 선택할 수 있다는 것입니다.

하위 문제를 사용하여 상태를 정의합니다. 즉, f[i][v]는 첫 번째 i 항목을 용량이 v인 배낭에 넣어 얻을 수 있는 최대값을 나타냅니다. 그러면 상태 전이 방정식은

f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }입니다.


rreee

위 내용은 Java에서 배낭 알고리즘을 구현하는 방법에 대한 예제 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.