2
루트 그래프가 제공됩니다. 여기서 노드는 가치있는 항목을 포함하는 "집"입니다. 엔트리 노드, 즉 그래프의 루트가 주어진다.주어진 경로 비용에서 최대 이익 계산
한 노드에서 다른 노드로 이동하기위한 비용, 즉 Egde 가중치도 부여됩니다.
질문 -
당신은 최대 가치있는 아이템을 수집해야하고, 총 비용은 주어진 비용을 초과하지 않아야합니다.
제한 - 1. 사이클이 없습니다. 2. 또한 adjancency 행렬을 사용할 수 있습니다 (정점의 총 개수는 1000 개까지입니다).
예
그들의 무게와 목적지 노드에서 본 값으로 주어진 가장자리.
0 1 10 1
0 2 10 15
1 3 50 10
1 4 30 30
을 감안할 때 비용 = 70
솔루션 - 당신은 노드 1, 2, 최대 방법 4의 항목을 수집합니다. [1 + 15 + 30 = 46]
내 노력
I 생각 모든 노드에서 어떤 상태를 유지하여, DP에 의해 해결할 문제점이. 하지만 일부 알고리즘을 만들 수 없습니다. 도와주세요. 1
-
편집이 질문은 각 노드에 몇 가지 상태를 ading에 의해 원래의 그래프를 사용하여 특수 그래프를함으로써 해결 될 수있다 생각합니다.
- 두 번째 방법은 동적 프로그래밍입니다.
이것은 숙제 솔루션 사이트가 아닙니다. 무언가를 시도했지만 작동하지 않는 이유를 알 수없는 경우 코드를 게시하면 부족한 부분을 강조 표시 할 수 있습니다. – PaulProgrammer
@PaulProgrammer 이것은 내 숙제가 아닙니다. 코드를 작성하기 전에 구체적인 알고리즘을 작성하려고했습니다. 그러나 나는 그것에 실패했다. 편집 1을 확인하십시오. – himanshu098
** 힌트 : ** 여행 판매원 문제에 대해 들어 보셨습니까? [http://en.wikipedia.org/wiki/Travelling_salesman_problem]? 이것은 단지 변형 일뿐입니다. – noMAD