일정 N 여행

Question

이 주어진 시간에 사람들은 퍼즐이지만, 나는 내가 모르고 나는 고전적인 알고리즘이 될 수 있다고 생각 : 산의 하단에 n 개의 사람들이 있습니다

을, 모두가 원하는 올라가고, 산을 내려 간다. 사람 i는이 산을 오를 시간이 필요하고, 내려갈 시간이 필요합니다.
그러나 동일한 시간에 at 사람이 오를 수 있습니다. 및입니다. atmost 1 명이 내려갈 수 있습니다. 산을 오르 내리는 가장 짧은 시간을 찾으십시오.

---

업데이트 1 :
잘 내가 몇 가지 예와 함께 노력하고 sorting, or getting the fastest climbers first 또는 그 반대로 환원 아니다 것을 발견했다. 우리가 가능한 모든 해결책을 시도해야 할 수 있습니다 optimal 솔루션을 얻을 수 있다고 생각하므로 NP complete 것 같습니다.

---

내 초기 추측 : 내가 생각 솔루션은 욕심
(잘못된) : 일종의 N 오름차순으로 시작 시간에 의해 사람들. 그런 다음 jth person up 및 kth down 인 경우 u[j]<= d[k] 및 d[k] is minimum from all k persons on top of mountain입니다. 나는 이것의 정확성을 증명할 수 없다.

---

다른 방법으로 접근하는 방법은 무엇입니까?
힌트로 충분합니다.

Answer 1

다음과 같은 방식으로 생각해보십시오. 사람이 오름차순으로 정렬되지 않은 경우 올바른 순서가 아닌 인접한 사람을 발견하면 일어나는 것보다 산에 오르는 것이 좋습니다 (예 : 첫 번째 것은 두 번째 것보다 오랫동안 올라갑니다). 총 시간이 늘어날 가능성이 있습니까?

Answer 2

내가 잘못 생각합니다. 귀하의 알고리즘은 0,1 주문 부여합니다

u = [2,3] 
d = [1,3] 

이 1,0을해야하는 반면 고려합니다.

• 이 ordering 목록을 만들고 첫 번째 사람을 추가

  나는 다른 욕심 접근 방식을 제안합니다. 현재 주문에 대한

두 값을 추적 :
• mU - 마지막
• mD의 시간 - - 최초의 이른 시간의 시간 명에서
• 내림차순 산에 마지막 사람의 시간 주문하지 않은 사람은 abs(mD - d)과 abs(mU - u)을 최소화하는 것을 선택하십시오. 그렇다면 abs(mD - d) < abs(mU - u) 그는 ordering의 시작 부분에 가야합니다. 그렇지 않으면 그는 최후에 간다.

여기에서 약간의 조정이 필요할 수도 있지만이 방법은 예제에 표시된 것과 같은 경우의 손실을 최소화해야합니다.

Answer 3

다음 용액은이 용액이 동적 프로그래밍 및 비트 마스크 기술 지식 이해 될 필요하다 < N = 24

작동한다.

관측 : 우리가 쉽게 최적의 총 상승까지 시간이 를 n 사람들의 총 상승까지 시간을 같게됩니다을, 고정 된 것을 관찰 할 수있다.

n = 1 인 경우 기본 경우에 대한 해결책이 분명합니다.

n = 2 인 경우 솔루션은 간단하지만 4 가지 가능성을 모두 스캔하여 최소 작동 중지 시간을 계산하면됩니다.

n = 3 인 경우이 경우는 한 사람이 처음 오르면 그 다음에 두 사람이 오르는 것과 같습니다. 두 사람의 최소 다운 타임은 쉽게 미리 계산할 수 있습니다. 더 중요한,이 두 사람은 으로 처리 될 수 있습니다. 최대 시간은 두 시간의 합계 시간이고, 작동 중지 시간은 최소 작동 중지 시간입니다. 비트 마스크 기법을 사용하여 'dp'라고하는 배열에서 n = 0에서 n = 3까지의 경우에 대한 최소 정지 시간에 대한 모든 결과를 저장하면 3 인의 상태를 인덱스 3 = 111b로 나타내므로 대소 문자 n에 대한 결과 = 3이 될 것이다 : N 들어

for(int i = 0; i < 3; i++){ 
     dp[3] = min(dp[(1<<i)] + dp[3^(1<<i)],dp[3]); 
} 

= 4 ... (24)는 상기 용액의 경우와 유사 할 것이다 N = 3

참고 실제 화학식 코드처럼 간단하지 않다 n = 3 인 경우 (n = 2와 비슷한 해결 방법이 필요함) 매우 유사하지만

Answer 4

현명한,하지만 그것은 지나치게 단순화 될 수 있습니다, 당신은 더 정확하게 여기서 설명 할 수 있습니까? 당신의 설명에서, 나는 당신이 분류하고 있는지 또는 다른 어떤 것이 있는지를 판단 할 수 없다;

• 먼저 빠른 등반을 받기 때문에 시작이 최대한 빨리 아래 경로 를 사용하여 이러한 내가 사용하는 생각 추론이다.
• 사람이 은 당신이 먼저 빠르게 상승하고 천천히 내려 사람들을 선택하는 것입니다 방법을 immediately.The 하강하기 시작, 아래로 경로를 사용할 수있을 때 사람들이 너무 이 산의 정상에 항상 존재해야합니다.

가장 빠른 등반가가 가장 빠른 디 센더 일 경우 어떻게해야합니까? 그러면 두 번째 등반가가 정상에 오를 때까지 다운 경로가 유휴 상태로 남을 것입니다. 알고리즘이 어떻게이 최적의 순서를 보장합니까? 문제가 정렬 문제로 줄어들지는 모르겠지만 배낭이나 스케줄링 유형과 비슷합니다.