지불금을 극대화 & I는 비용이 Y 금액 이상 이동하지 않고 대부분의 성향을 생산 X 노드를 찾기위한 알고리즘이 있나요 100 개 노드가 각각 (지급 비용)</p> <p>로 구성된이 있다고 가정하자 X

Question

아래의 비용을 유지?

저는 알고리즘 문제를 처음 접했고 단순한 정렬 알고리즘이 있는지 또는 어떻게 든 가중치 트리를 만들었는지 확실하지 않습니다. 아니면 용감한 방법일까요?

예 :
우리는 20 비용 이상하지 않고 3 개 노드에서 출발하는 가장 지불금을 원하는

노드 [] = (10, 8), (7, 8), (6, 7), (5 3) (11, 14)

최상의 결과 (10, 8), (7,8), (5, 3)
대금 = 22
비용 = 19


답을 모르는 경우, 어떤 알고리즘 범주인지, 또는 내가 조사해야하는 것과 같은 용어 측면에서 올바른 방향을 제시해 주시면 감사하겠습니다. 감사!

Answer 1

이것은 0/1 knapsack problem이라는 유명한 문제이며이를 해결하는 데 사용할 수있는 방법이 많이 있습니다. 가장 쉽고 효율적인 솔루션 중 하나는 요소를 한 번에 하나씩 고려하는 동적 프로그래밍 알고리즘입니다. 이 용어를 염두에두고 스택 오버플로 (stack overflow) 또는 인터넷 전반에 걸쳐 훌륭한 리소스를 찾을 수 있어야한다고 생각합니다.