JS 튜토리얼--동적 프로그래밍 알고리즘의 배낭 용량 문제

배낭 문제

Question
Given N개 항목 및 용량 V# 🎜🎜 #님의 배낭, 항목 i의 부피는 wi이고 값은 ci입니다.
(각 품목은 하나만 있습니다)Q: 배낭에 넣을 품목의 총 가치가 최대화되도록 배낭에 넣을 품목을 선택하는 방법 ?

각 항목을 보면 넣을지 안 넣을지 두 가지 선택만 가능합니다. 각 항목은 한 번만 넣을 수 있습니다.

이전과 같은 방법으로 시도해 보겠습니다

마지막 항목만 남았다고 가정하면 두 가지 옵션이 있습니다
1 공간이 충분하면 Enter를 선택합니다.
2. 남은 공간이 부족할 경우

을 넣지 마십시오. 따라서 두 가지 최적의 하위 구조가 있습니다.

1. i-1 아이템을
2에 넣는 최적의 선택 V-w[i]#🎜🎜 # 요약하면 다음과 같습니다.

i 항목을 V 용량의 배낭에 넣는 최적의 선택: ​​

max(i-1을 V 용량의 백팩 최적의 아이템 선택, 용량의 백팩에 i-1 아이템을 담는 최적의 선택 V-w[i] + c[i])
We f[i] [v]를 사용하면 첫 번째 i개 항목을 용량 v인 배낭에 넣어 얻을 수 있는 최대값을 나타냅니다.

하위 문제를 사용하여 상태 정의:

상태 전이 방정식은 다음과 같습니다.
f[i] [v] = max{f[i-1] [v],f[i- 1] [v-w[i]]+c[i]}
. 먼저

백팩의 총 용량은 V = 12

항목의 용량 배열은 w = [4, 6, 2, 2, 5, 1 ]
값 배열은 c = [8, 10, 6, 3, 7, 2]

1. f(i,v)입니다. = 0 (i
2. f(i,v) = c[0 ] (i==1 , v>=p[0]);

3. f(i,v) = f(i -1,v) ( i>1, v
4. f(i,v) = max(f(i- 1,v), f(i-1,v-w[i-1])+c[i-1])(i>1, v>=w[i-1])#🎜🎜 #

   # 🎜🎜#

왼쪽에서 오른쪽으로 갈 때마다 이전 데이터가 저장됩니다

갈 때 위에서 아래로 이전 행의 데이터를 저장합니다.그래서 일반적으로 한 행의 데이터만 저장하면 됩니다. 공간 복잡도는 O(V)

시간 복잡도는 O(N*V)입니다. , 공간 복잡도는 O(V)입니다.

그러나 원래의 재귀 방법, 즉 순열 및 조합 방법을 사용하면 시간 복잡도는 O(2^N)입니다.# 🎜🎜##🎜🎜 #그러면 V가 매우 크고 N이 작을 때, 예를 들어 V=1000이고 N=6일 때 재귀는 2^6=64번만 계산하면 됩니다. 반면 매우 존경받는 동적 프로그래밍에는 다음이 필요합니다. 계산 1000*6=6000회# 🎜🎜#
따라서 절대적으로 좋고 나쁜 알고리즘은 없으며 핵심은 응용 상황에 따라 다릅니다

관련 권장 사항:

#🎜 🎜#
JS로 동적 프로그래밍 Backpack 알고리즘 구현

JavaScript 고급 알고리즘 동적 프로그래밍 예제 분석

위 내용은 JS 튜토리얼--동적 프로그래밍 알고리즘의 배낭 용량 문제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!