그래서 인터뷰 중에이 질문을 보았지만 해결할 수 없었습니다. 누군가가 조언 할 수 있기를 바랍니다. 문제는 이것입니다.
정수로 S 금액을 절약했다고 상상해보십시오. 주식 매입을 생각하고 있습니다. 누군가가 N 크기의 주식 구매 가격 배열 2 개와 다음 날 판매 가격을 제공했습니다. S와 2 개의 배열을 받아 들일 수있는 알고리즘을 작성하고 다음날 달성 할 수있는 최대 수익을 반환합니다. 두 배열의 길이가 같습니다. 첫 번째 배열의 인덱스 i에있는 숫자는 i 번째 주식의 구매 가격을 보여주고 두 번째 배열의 인덱스 i에있는 숫자는 i 번째 주식의 판매 가격을 보여줍니다.
예. S = 10, buy_price = [4, 6, 5], sell_price = [6, 10, 7], 당신의 저축은 10이고, 3 개의 스톡 옵션이 있습니다. 첫 번째 옵션은 구매 가격이 4이고 판매 가격은 다음날 6입니다. 두 번째 옵션 구매 가격은 6이고 판매 가격은 다음날 10입니다. 등등. 여기에서 최대 수익은 6이며, 가격이 4와 6 인 스톡 옵션을 매수하고 다음날 매도합니다. 여기서 함수는 6을 반환해야합니다.
저의 초기 접근 방식은 각 주식의 수익 / 비용 비율을 찾아 분류하는 것이 었습니다. 그러나 이것은 가장 이상적인 주식 구매로 이어지지 않을 수 있습니다. 예를 들어,이 경우 S = 10, buy_price = [6, 5, 5], sell_price = [12, 9, 8]가장 좋은 방법은 수익 / 비용 비율이 가장 높지만 (남은 저축액 4 개로 아무것도 살 수 없음) 가격이 6 인 주식을 사는 것이 아니라 다른 2 개의 스톡 옵션을 사는 것입니다. 최대 이익은 7입니다.
누구든지이 문제를 해결하는 방법을 알고 있습니까? 감사합니다!
가격을 가중치로, 이익을 가치로 간주한다면이 문제는 정확히 0/1 배낭 문제 입니다. 이 문제는 약하게 NP- 완전합니다. 즉, 입력 크기의 함수로서 다항식 시간 알고리즘은 없지만 동적 프로그래밍을 사용하면 예산 함수로서 다항식 시간에이 문제를 해결할 수 있습니다.
따라서 예산이 합리적으로 적 으면 동적 프로그래밍 방식으로이 문제를 효율적으로 해결할 수 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다