중화사전망 - 서예자전 - 배낭 문제
배낭 문제
DD 소의 배낭 9 강
P0 1: 0 1 배낭 문제
과목
N 개 물품과 용량이 V 인 배낭 1 개, 제 I 품목 비용은 C, 가치는 W, 어떤 물건을 배낭에 넣어야 하는지 해결하면 이들 물품의 총비용이 배낭의 용량을 초과하지 않고 총가치가 가장 크다. (알버트 아인슈타인, Northern Exposure (미국 TV 드라마), 예술명언)
기본 생각
이것은 가장 기본적인 배낭 문제이며, 각 물품이 하나뿐이며, 놓거나 놓지 않을 수 있는 것이 특징이다.
하위 질문으로 상태를 정의합니다. 즉, f[v] 는 처음 I 개 항목이 용량이 v 인 배낭에 넣기만 하면 얻을 수 있는 최대값을 나타냅니다. 상태 전이 방정식은 f[v]=max{f[v], f[v-c]+w}
이 방정식은 매우 중요합니다. 기본적으로 모든 배낭 문제와 관련된 방정식은 그것으로부터 파생됩니다. 따라서 첫 번째 I 항목만 놓을 수 없는 전략만 고려한다면 "첫 번째 I 항목을 V 의 배낭에 넣는다" 는 하위 문제는 첫 번째 I- 1 항목만 포함하는 문제로 전환될 수 있습니다. 만약 I 항목이 놓지 않으면 문제는' I- 1 항목이 V 용량의 배낭을 넣는다' 로 바뀐다. I 번째 아이템을 넣으면 문제는' I- 1 개 아이템을 나머지 v-c 용량의 배낭에 넣는다' 로 전환된다. 이때 얻을 수 있는 최대값은 f [v-c] 에 I 아이템을 넣어 얻은 값 W 를 더한 것이다.
F[v] 는 의미가 있고 상위 I 항목의 하위 집합이 있는 경우에만 총 비용이 v 이므로 이 방정식에 따라 재귀적으로 진행한 후 최종 대답은 f[N] [V] 가 아니라 f [n] [0 의 최대값 ... 5] 입니다. 만약' cha-cha' 라는 단어를 상태의 정의에서 빼면, 이전 방정식에 추가 f[v- 1] 가 추가되어 f[N] [V] 가 최종 답임을 보증한다. 왜 이렇게 할 수 있는지에 관해서는, 네가 스스로 이해하느냐에 달려 있다.
공간 복잡성 최적화
위 방법의 시간과 공간 복잡성은 모두 O(N*V) 입니다. 여기서 시간 복잡성은 거의 최적화되지 않지만 공간 복잡성은 O(V) 로 최적화될 수 있습니다.
먼저 위에서 언급 한 기본 아이디어를 실현하는 방법을 고려하십시오. 주 루프 I = 1...n 과 2 차원 배열 F [0...v] 는 한 번에 계산됩니다. 그런 다음 배열 f [0..V] 가 하나만 사용되는 경우, 우리가 정의한 상태 f[v] 가 첫 번째 루프 뒤에 f[v] 로 표시된다고 보장할 수 있습니까? F[v] 는 두 개의 하위 질문 f[v] 와 f [v-c] 에 의해 재귀적으로 내보내집니다. F[v] 가 밀릴 때 f[v] 가 f[v] 와 f[v -c] 의 값을 얻을 수 있는지 확인할 수 있습니까? 실제로 f[v-c] 가 f[v] 를 밀면서 상태 f[v-c] 의 값을 저장할 수 있도록 v=V 순서로 f[v]..0 을 밀어야 합니다. 의사 코드는 다음과 같습니다.
I= 1 .. 보통
V=V..0 의 경우
F [v] = 최대 {f [v], f [v-c]+w};
문장 f[v]=max{f[v], f[v-c]} 는 우리의 전달 방정식 f[v]=max{f[v], f[v-c]} 와 정확히 같습니다 V 의 순환 순서를 위에서 역순으로 바꾸면 f[v] 는 f[v-c] 에서 파생되는데, 이는 f [v-c] 의 의미와 맞지 않지만 또 다른 중요한 배낭문제 P02 의 가장 간단한 해법이므로 1 차원 배열로만 0 1 배낭 문제를 해결하는 법을 배우는 것이 필요하다
요약
0 1 배낭 문제는 가장 기본적인 배낭 문제이며 배낭 문제 중 가장 기본적인 설계 상태와 방정식의 사상을 담고 있습니다. 또한 다른 유형의 배낭 문제는 종종 0 1 배낭 문제로 변환될 수 있습니다. 따라서, 우리는 위의 기본 사상의 그리기 방법, 상태 전이 방정식의 의미, 그리고 마지막으로 공간의 복잡성을 최적화하는 방법을 자세히 이해해야 한다.
P02: 완전한 배낭 문제
과목
N 가지 물품과 V 용량의 배낭이 하나 있는데, 각 물품마다 수량이 제한이 없습니다. 물품 I 의 원가는 C 이고, 가치는 W 이며, 어떤 물품을 배낭에 담았는지 해결하면 이들 물품의 총비용이 배낭의 용량을 초과하지 않고 총가치가 가장 크다.
기본 생각
이 문제는 0 1 배낭 문제와 비슷하지만 모든 물건이 무한하다. 즉, 각 항목에서 관련 전략은 2 를 취하거나 취하지 않고 0, 1, 2 등을 취하는 것이다. 여전히 0 1 배낭을 푸는 생각대로라면 f[v] 는 방금 V-용량의 배낭을 넣은 처음 I 개 품목의 최대 중량을 나타내고, 상태 전이 방정식은 각 품목의 다른 전략에 따라 이렇게 쓸 수 있다. F [V] = Max {F [V-K]
0 1 배낭 문제의 기본 사상을 개선하여 이렇게 명확한 방법을 얻었다. 이는 0 1 배낭 문제의 방정식이 확실히 중요하며 다른 유형의 배낭 문제로 확대될 수 있다는 것을 보여준다. 하지만 우리는 여전히 이런 복잡성을 개선하려고 노력하고 있습니다.
간단하고 효율적인 최적화
완전한 배낭 문제에는 간단하고 효과적인 최적화가 있습니다. 만약 두 가지 품목 I 와 J 가 C 를 충족한다면, =w[j] 이면 j 항목 제거가 고려되지 않습니다. 이러한 최적화의 정확성은 분명합니다. 어쨌든 저가의 고비용 J 는 적어도 더 나쁜 방안은 얻을 수 없는 저렴한 I 로 대체할 수 있습니다. 무작위로 생성된 데이터의 경우 이 방법은 종종 항목 수를 크게 줄여 속도를 높입니다. 그러나, 이것은 특별히 설계된 데이터가 사라지지 않을 수 있기 때문에 최악의 상황의 복잡성을 개선하지 못했다.
0 1 배낭 문제 해결로 변환.
0 1 배낭 문제가 가장 기본적인 배낭 문제이므로 전체 배낭 문제를 0 1 배낭 문제로 전환하여 해결할 수 있습니다. 가장 간단한 아이디어는 V/c 항목이 I 번째 항목이 가장 많이 선택되었다는 점을 감안하면 I 항목을 V/c 항목과 비용 및 가치가 같은 항목으로 변환한 다음 0 1 배낭 문제를 해결할 수 있다는 것입니다. 이는 기본 사상을 개선하는 시간의 복잡성은 전혀 없지만, 완전한 배낭 문제를 0 1 배낭 문제로 바꾸는 아이디어를 준다. 한 물건을 여러 물건으로 분해하는 것이다.
보다 효율적인 변환 방법은 제 I 조를 C * 2 K 비용, 가치 W * 2 K 로 나누는 것입니다. 여기서 k 는 C * 2 K 를 충족합니다
이 의사 코드와 P0 1 의 의사 코드는 V 의 순환 순서에서만 다르다는 것을 알 수 있습니다. 왜 이런 변화가 가능할까요? 먼저 P0 1 v=V 의 역순 루프 ... 0 ... I 루프의 상태 f[v] 가 상태 f[v-c] 에서 재귀적으로 파생되어야 하기 때문입니다. 즉, 이는 각 항목이 한 번만 선택되도록 하기 위한 것으로, "항목 I 선택" 정책을 고려할 때 항목 I 에 선택되지 않은 하위 결과 f[v-c] 를 기준으로 합니다. 현재 완전 백팩의 특징은 각 항목을 무제한으로 선택할 수 있다는 점이다. 따라서' I 항목 추가' 전략을 고려할 때 이미 I 항목으로 선택되었을 수 있는 하위 결과 f[v-c] 가 필요하기 때문에 v = 0 의 순차 루프를 채택하는 것이 가능하고 필요한 ... 이것이 바로 이 간단한 프로그램을 만드는 이유이다.
이 알고리즘은 다른 방법으로도 얻을 수 있다. 예를 들어, 기본 사상에서의 상태 전이 방정식은 f[v]=max{f[v], f[v-c]+w}, 1 차원 배열로 이 방정식을 구현하면 위의 의사 코드를 얻을 수 있습니다.
요약
완전한 배낭 문제도 매우 기본적인 배낭 문제이며, 각각' 기본 사상' 과' O(VN) 알고리즘' 장에 두 가지 상태 전이 방정식이 있습니다. 여러분이 이 두 가지 상태 전이 방정식을 자세히 이해할 수 있기를 바랍니다. 기억해야 할 뿐만 아니라, 그것들이 어떻게 파생되었는지 이해해야 합니다. 스스로 이 방정식들을 얻을 수 있는 방법을 찾는 것이 가장 좋다. 사실, 그 방정식의 의미에 대해 생각해 보면, 어떻게 얻을 수 있는지는 동적 계획에 대한 이해를 깊게하고 동적 계획 기술을 향상시키는 좋은 방법입니다. (데이비드 아셀, Northern Exposure (미국 TV 드라마), 방정식명언)
P03: 다중 배낭 문제
과목
N 가지 물품과 용량이 V 인 배낭이 있습니다. 최대 N 개 품목 I 를 사용할 수 있습니다. 각 물건의 비용은 C 이고, 가치는 W 입니다. 어떤 물건을 배낭에 넣어야 하는지 풀면 이들 물품의 총 비용이 배낭의 용량을 초과하지 않고 총 가치가 가장 큽니다. (존 F. 케네디, Northern Exposure (미국 TV 드라마), 예술명언)
기본 알고리즘
이 제목은 완전한 배낭 문제와 매우 비슷하다. 기본 방정식은 완전한 배낭 문제의 방정식을 약간 바꾸면 된다. 제 1 항은 n+ 1 개 전략: 0 개, 1 항목 ... N 개 항목을 취한다. F[v] 는 방금 v 용량의 배낭을 넣은 앞 I 품목의 최대 중량을 나타냅니다. f [v] = max {f [v-k * c]+k * w | 0
0 1 배낭 문제로 변환
생각하고 쓰기 쉬운 또 다른 기본 방법은 0 1 백팩으로 변환하는 것입니다. 0 1 백팩의 I 번째 아이템을 N 개 아이템으로 대체한 다음, 항목 수가 N 인 0 1 배낭 문제를 직접 해결하는 것입니다.
그러나 이를 0 1 배낭 문제로 전환한 후 완전한 배낭으로서의 복잡성을 줄일 것으로 기대합니다. 아니면 이진적인 생각을 고려해 볼 때, 우리는 제 1 항을 몇 항목으로 대체하는 것을 고려해 볼 때, 원래 문제에서 제 I 항목이 취할 수 있는 모든 전략, 즉 0...n 을 취하는 것은 다음 몇 가지를 몇 가지로 대체하는 것과 같을 수 있다. (윌리엄 셰익스피어, 윈스턴, 이진명언) (윌리엄 셰익스피어, 윈스턴, 이진명언) 또한 N 블록 이상의 전략은 반드시 나타나서는 안 된다.
방법은: I 조를 여러 개로 나누고, 각각 이 비용과 가치에 원래의 비용과 가치를 곱하는 계수가 있다. 이러한 계수가 1, 2,4, ..., 2 (k- 1), n-2 k+ 1, k 가 n-220 을 충족한다고 가정합니다 예를 들어, n 이 13 인 경우, 이 문장 는 각각 1, 2,4,6 의 계수로 네 편으로 나뉜다.
이러한 분할 항목의 계수 합은 N 으로, N 개 이상의 첫 번째 클래스 항목을 가져올 수 없음을 나타냅니다. 또한, 이 방법은 0..n 이 몇 가지 계수의 합계로 표현될 수 있도록 보장할 수 있다. 이 증명서는 0..2 k- 1 과 2 k..n 의 두 부분으로 나눌 수 있습니다. 어렵지 않습니다. 네가 스스로 생각해 보길 바란다.
이렇게 하면 I 항목을 O(log n) 항목으로 나누고, 원래 문제를 O (V * * Logn) 의 0 1 배낭 문제로 변환하는 것은 큰 개선이다.
O(VN) 알고리즘
다중 배낭 문제에도 O(VN) 알고리즘이 있습니다. 이 알고리즘은 기본 알고리즘에 기반한 상태 전환 방정식이지만 각 상태의 값은 단조로운 큐잉 방법을 사용하여 평균 O( 1) 시간 내에 해결할 수 있습니다. 단조로운 대기열 최적화 DP 가 NOIP 범위를 벗어났기 때문에 이 문서에서는 더 이상 자세히 설명하지 않습니다. 나는 이 방법이 건물 천성의' 남자 팔문' 슬라이드에 있다는 것을 처음 알았다.
요약
여기서 우리는 알고리즘의 복잡성이 O (V * * N) 에서 O (V * * Log N) 로 높아지는 과정을 보았고, 우리는 또한 O(VN) 알고리즘이 있다는 것을 알게 되었다. 그 응용지식은 NOIP 의 범위를 넘어섰다. 여러분이' 항목 분할' 의 사고방식과 방법에 각별히 주의를 기울이고, 그 정확성을 증명하고, 가능한 간단한 프로그램 실현을 위해 최선을 다하시기 바랍니다.
P04: 혼합 3 배낭 문제
문제
P0 1 인 경우 P02 와 P03 이 혼합됩니다. 즉, 어떤 물품은 한 번만 휴대할 수 있고 (0 1 배낭), 어떤 물품은 무한히 휴대할 수 있고 (완전 배낭), 어떤 물품은 상한밴드 (복수 배낭) 를 가질 수 있다. 어떻게 해결해야 하나요?
0 1 배낭과 완전 백팩의 혼합
P0 1 과 P02 에 제공된 의사 코드에는 단 하나의 차이점이 있다는 점을 감안할 때, 한 상품은 한 번만, 다른 상품은 무한히 받을 수 있는 두 가지 상품만 있을 경우 각 상품에 이전 방정식을 적용할 때 상품의 범주에 따라 순서 또는 역순환을 선택하기만 하면 됩니다. 복잡성은 O(VN) 입니다. 의사 코드는 다음과 같습니다.
I= 1 .. 보통
I 번째 아이템이 0 1 배낭인 경우
V=V..0 의 경우
F [v] = 최대 {f [v], f [v-c]+w};
그렇지 않으면 프로젝트 I 가 완전한 배낭인 경우
V=0..V 의 경우
F [v] = 최대 {f [v], f [v-c]+w};
플러스 여러 배낭
일부 물품이 최대 제한 시간을 받을 수 있는 경우 원칙적으로 O(VN) 에 대한 해석을 제공할 수 있습니다. 여러 배낭 유형의 품목은 단조로운 대기열로 해결할 수 있습니다. 하지만 NOIP 범위 밖의 알고리즘을 고려하지 않고 P03 으로 이들 아이템을 각각 O(log n) 0 1 배낭 아이템으로 나누는 방법은 이미 우수하다.
요약
어려운 주제들은 모두 간단한 주제들이 겹겹이 겹친다는 말이 있다. 이 말이 공리인지 아닌지는 잠시 말하지 않았지만, 이번 강의에서는 이미 충분히 구현되었다. 원래 0 1 배낭, 완전 배낭, 멀티 백팩도 어려운 문제가 아니었지만 간단하게 조합한 뒤 이런 문제가 생겨 많은 사람들을 놀라게 할 것이다. 그러나 견고한 기초를 가지고 세 가지 기본 배낭 문제의 사상을 이해하면 어려운 문제를 간단한 문제로 분해하여 해결할 수 있다.
P05: 2 차원 배낭 문제
문제
2 차원 비용의 배낭 문제는 각 품목에 대해 두 가지 다른 비용이 있다는 것입니다. 이 항목을 선택하면 두 가지 비용을 동시에 지불해야합니다. 각 가격에는 지불할 수 있는 최대 값 (배낭 용량) 이 있습니다. 물건을 어떻게 선택해야 최대의 가치를 얻을 수 있는지 가르쳐 주세요. 이 두 가지 비용을 각각 1 과 2 로 설정하고, 제 I 조에 필요한 두 가지 비용은 각각 A 와 B 입니다. 두 가지 비용 (두 가지 배낭용량) 이 지불할 수 있는 최대값은 각각 V 와 U 입니다. 문장 가치 W.
알고리즘
비용에 차원을 더하고 상태에 차원을 하나 더합니다. F[v] 는 처음 I 항목이 각각 두 개의 가격 v 와 u 를 지불할 때 얻을 수 있는 최대값을 나타냅니다. 상태 전이 방정식은 f [v]=max{f[v], f[v-a]]+w} 입니다. 앞서 언급했듯이 2 차원 배열만 사용할 수 있습니다. 즉, 항목당 한 번만 가져올 수 있는 경우 변수 V 와 U 는 순차 루프를 사용하고, 항목이 전체 배낭 문제와 같은 경우 역방향 루프를 사용합니다. 여러 개의 배낭 문제처럼 물품을 분할하다.
총 문장 수 제한
때로는 "2D 비용" 조건이 암시적으로 주어질 수 있습니다. 최대 M 개 항목만 사용할 수 있습니다. 이것은 실제로 상품당' 조각 수' 를 한 개 더 추가한 것과 같다. 품목당 건수는 1 으로 최대 m 건까지 지불할 수 있습니다 ... 즉, f[v][m] 이 당신이 V 를 지불하는 비용을 대표하도록 하고, M 품목을 선택할 때 얻을 수 있는 최대값까지 선택하고, 품목 유형 (0/Kloc-0) 을 기준으로 합니다
또한 "m 항목만" 을 요청하면 대답은 f[0..V][M] 입니다.
요약
사실, 익숙한 동적 계획 문제의 변형으로 인한 문제를 발견할 때, 원래 상태에 평행선을 추가하여 새로운 제약을 충족시키는 것이 일반적인 방법이다. 이번 강의에서 이 방법을 초보적으로 이해할 수 있기를 바랍니다.
P06: 그룹 배낭 문제
문제
N 개 물품과 용량이 V 인 배낭 1 개, I 품목 비용은 C, 가치는 W 로 나뉜다. 이들 품목은 여러 그룹으로 나뉘어 각 그룹 내 물품이 서로 충돌하기 때문에 최대 한 가지 물품만 선택할 수 있다. 어떤 물건을 배낭에 담았는지 해결하면 이들 물품의 총 비용이 배낭의 용량을 초과하지 않고 총 가치가 가장 크다.
알고리즘
이 질문은 각 항목 그룹마다 그룹 내의 항목을 선택할지 여부에 대한 몇 가지 전략이 됩니다. 즉, f[k][v] 가 상위 k 그룹 상품 비용 v 가 얻을 수 있는 최대 중량을 나타내는 경우 f [k] [v] = max {f [k- 1] [v],,
1 차원 배열을 사용하는 의사 코드는 다음과 같습니다.
모든 k 그룹에 대해
왜냐하면 나는 K 팀에 속해 있기 때문이다.
V=V..0 의 경우
F [v] = 최대 {f [v], f[v-c]+w}
또한 P02 의 "간단하고 효과적인 최적화" 를 각 그룹의 항목에 적용할 수 있습니다.
요약
그룹 배낭 문제는 상호 배타적인 아이템 몇 개를 한 그룹이라고 부르며 좋은 모델을 만들었다. 배낭 문제의 많은 변종은 그룹 배낭 문제 (예: P07) 로 전환될 수 있으며, 그룹 배낭 문제에서' 광의항목' 이라는 개념을 추가로 정의할 수 있어 문제 해결에 유리하다.
P07: 배낭 의존 문제
문제를 단순화하다
이 배낭 문제의 항목 사이에는 일정한' 의존성' 관계가 있다. 즉, I 는 j 에 의존합니다. 즉, I 항목을 선택하면 j 항목을 선택해야 합니다. 간단히 하기 위해, 우리는 다른 항목에 의존하고 의존하는 항목이 없다고 가정합니다. 또한 한 프로젝트도 동시에 여러 프로젝트에 의존하지 않습니다.
알고리즘
이 문제는 NOIP2006 김명 예산 계획에서 연장된 것이다. 이 문제에 대한 제법에 따르면 다른 항목에 의존하지 않는 항목을' 주요 부분' 이라고 하고, 한 주요 부분에 의존하는 항목을' 첨부 파일' 이라고 한다. 이 문제의 단순화 조건에 따라 모든 프로젝트는 몇 가지 주요 부분과 각 주요 부분에 의존하는 하나의 첨부 파일 세트로 구성됩니다.
배낭문제의 일반적인 사상에 따르면 하나의 주요 부분과 그 부속집만 고려한다. 하지만 사용 가능한 많은 전략이 있습니다. 예: 없음, 주요 부분만, 주요 부분을 선택한 후 첨부 파일이 하나 있고, 주요 부분을 선택한 후 첨부 파일이 두 개 있습니다. 그래서 많은 정책은 상태 전환 방정식으로 표현할 수 없습니다. (실제로 n 개의 첨부 파일이 있고 정책 수는 2 n+ 1 이며 기하급수적입니다. ) 을 참조하십시오
이러한 모든 정책이 상호 배타적이라는 점을 감안할 때 (즉, 하나의 정책만 선택할 수 있음), 주 및 해당 첨부 파일 세트는 실제로 P06 의 항목 그룹에 해당하며, 주 및 여러 첨부 파일을 선택하는 각 정책은 이 항목 그룹의 한 항목에 해당합니다. 그 비용과 가치는 이 정책의 항목 가치의 합계입니다. 그러나 이 단계의 전환만으로는 좋은 알고리즘을 제공할 수 없다. 프로젝트 그룹의 프로젝트는 여전히 원래 문제의 전략만큼 많기 때문이다.
P06 의 한 문장을 고려해 보십시오. P02 의 "간단하고 효과적인 최적화" 를 각 그룹의 항목에 적용할 수 있습니다. 이는 한 프로젝트 그룹 내의 프로젝트에 대해 모든 비용이 같은 프로젝트가 최대값에 불과하며 결과에 영향을 주지 않는다는 것을 상기시켜줍니다. 그래서 우리는 먼저 바디 섹션 I 의' 액세서리 컬렉션' 을 0 1 백팩으로 하여 상응하는 최대 f' [0 .. 원가가 0 일 때 ... v-c 를 차례로 얻을 수 있습니다. 그러면 주요 부품과 그 액세서리의 집합은 V-c+ 1 품목의 모음과 같습니다. 여기서 c+k 비용이 드는 물품의 가치는 F' [K]+W 입니다. 즉, 원래의 지수 전략이 많이 불필요하다는 뜻입니다. 0 1 의 배낭 후 주요 부분 I 는 V-c+ 1 개 항목의 품목 그룹으로 변환되어 P06 알고리즘을 사용하여 직접 문제를 해결할 수 있습니다.
더 일반적인 문제
더 일반적인 문제는 의존성이 도론에서' 숲' 으로 제공된다는 점이다. (숲은 여러 가지 나무의 집합임) 즉, 주체 부분의 첨부는 여전히 자신의 첨부 파일 세트를 가질 수 있다는 것이다. 한계는 각 항목마다 최대 한 가지 (하나의 주체 부분) 만 의존하고 순환 의존은 없다는 것이다.
이 문제를 해결하기 위해 각 주요 부분과 해당 첨부 파일을 프로젝트 그룹으로 변환하는 방법을 계속 사용할 수 있습니다. 유일한 차이점은 액세서리가 있을 수 있기 때문에 각 액세서리는 일반 0 1 백팩의 품목으로 간주해서는 안 된다는 것입니다. 이 첨부에도 첨부 세트가 있는 경우 먼저 품목 그룹으로 변환한 다음 그룹 배낭 문제를 사용하여 주요 품목 및 해당 첨부 세트에 해당하는 첨부 그룹의 각 비용에 대한 첨부 값을 해결해야 합니다.
사실, 이것은 트리 DP 의 일종으로, 각 상위 노드가 하위 노드의 속성 DP 에 한 번 있어야 자신의 관련 속성을 얻을 수 있다는 특징이 있습니다. 이것은 이미' 광의상품' 의 개념을 건드렸다. P08 을 보면, 이' 종속 트리' 의 각 하위 트리가 하나의 넓은 의미의 항목과 같고, 노드 기반 하위 트리에 해당하는 넓은 의미의 항목을 찾는 것은 그 모든 하위 트리에 해당하는 넓은 의미의 합계를 찾는 것과 같다는 것을 알 수 있다. (알버트 아인슈타인, Northern Exposure (미국 TV 드라마), 종속 트리, 종속 트리, 종속 트리)
P08: 일반 조항
정의
이런 물건을 고려해 볼 때, 그것은 고정 비용과 가치가 없지만, 그 가치는 당신이 그것을 할당하는 비용에 따라 변한다. (존 F. 케네디, 돈명언) 이것은 넓은 의미의 상품의 개념이다.
더욱 엄격한 정의. 배낭 용량이 V 인 배낭 문제에서 넓은 의미의 항목은 정의 필드가 0 인 정수의 함수인 H .. 5, 할당된 비용이 V 일 때 얻을 수 있는 가치는 h(v) 입니다.
이 정의는 좀 추상적이다. 또 다른 이해는 넓은 의미의 항목이 배열 h[0 .. 5] 라는 것이다. 비용 v 를 주면 h[V] 값을 얻을 수 있습니다.
비용이 C 이고, 값이 W 인 아이템, 0 1 인 배낭에 있는 아이템인 경우 넓은 의미의 아이템으로 간주되고, H (C) = W 를 제외한 모든 함수 값이 0 인 함수입니다. 완전한 배낭에 있는 아이템인 경우 V 만 C 로 나눌 수 있고, 다른 모든 함수 값은 다음과 같습니다. 여러 배낭에서 반복되는 n 의 가장 큰 항목이라면 해당 일반화 항목의 함수는 h(v)=v/c*w 가 c 와 v/c 로 나눌 수 있는 경우에만 가능합니다
항목 그룹은 일반화 된 항목 h 로 볼 수 있습니다. 0 의 V..V 의 경우 항목 그룹에 V 비용이 있는 항목이 없으면 h(v)=0 입니다. 그렇지 않으면 h(v) 는 모든 비용이 V 인 항목의 최대값입니다. P07 에서 각 주요 부품 세트와 해당 액세서리는 하나의 항목 그룹에 해당하므로 넓은 의미로 간주될 수 있습니다.
일반화된 항목의 합계
만약 두 개의 광의상품 H 와 L 을 마주하고 있다면, 어떻게 주어진 비용으로 이 두 광의상품으로부터 최대의 가치를 얻을 수 있습니까? 실제로 주어진 비용 V 에 대해 이 비용을 두 개의 넓은 의미의 프로젝트에 어떻게 배분할 수 있는지 나열하기만 하면 됩니다. (윌리엄 셰익스피어, 윈스턴, 비용, 비용, 비용, 비용, 비용, 비용, 비용, 비용) 마찬가지로 0 의 각 정수 v..v 에 대해 h 와 l 에 할당된 비용 v 의 최대 f(v) 를 얻을 수 있습니다. 즉 f (v) = 최대 {h (k)+l (v-k) | 0 입니다
이를 통해 일반화 항목의 합계를 정의할 수 있습니다. h 와 l 은 f (v) = max {h (k)+L (v-k) | 0 을 충족하는 경우 모두 일반화 항목입니다
광의항목의 정의는 한 배낭 문제에서 두 개의 광의항목의 합계로 대체하면 문제의 답이 영향을 받지 않는다는 것을 보여준다. 사실, 모든 항목이 광의항목의 배낭 질문에 대한 답을 구하는 과정이며, 이 모든 광의항목의 합계를 구하는 과정이다. 이것을 S 로 설정하면 답은 s[0] 의 최대 .. 5] 입니다.
배낭 문제의 넓은 의미
배낭 문제에서 각 항목의 비용과 가치, 항목 간의 그룹화 및 종속성 등을 포함한 많은 조건이 주어질 수 있습니다. 그러나 문제를 일반화된 항목에 명시적으로 매핑할 수 있습니다. 즉, 모든 조건이 주어진 후, 각 음수가 아닌 정수 V 를 구할 수 있습니다. 배낭 용량이 V 인 경우 배낭에 물건을 적재할 수 있는 최대값은 얼마입니까? 음수가 아닌 정수 세트에 정의된 넓은 의미로 볼 수 있습니다. 이 일반화된 객체 (또는 정의필드가 음수가 아닌 정수인 함수) 에는 문제 자체의 고도로 집중된 정보가 포함되어 있습니다. 일반적으로 하위 도메인의 값 (예: 0..v) 을 찾는 넓은 의미의 항목에서 이 함수 값에 따라 배낭 질문에 대한 최종 답을 얻을 수 있습니다.
요약하자면, 일반적으로 배낭 문제를 해결하는 것은 이 문제를 해결하는 함수, 즉 이 문제의 넓은 의미이다. 넓은 의미의 항목을 해결하는 한 가지 방법은 그것을 몇 개의 넓은 의미의 합계로 표시한 다음 그것을 구하는 것이다.
요약
이 강의는 모두 내 자신의 오리지널이라고 할 수 있다. 구체적으로, 나는 함수형 프로그래밍의 체계 언어를 배울 때 함수형 프로그래밍의 관점에서 각종 배낭 문제를 고찰했다. 이 강의는 정말 추상적입니다. 아마도' 모델의 추상화 정도' 에서 이미 NOIP 의 요구 사항을 초과했기 때문에 잠시 알아듣지 않아도 괜찮습니다. OI 의 길이 점차 확장됨에 따라 언젠가는 알게 될 것이라고 믿는다.
저는' 사고' 가 OIer 의 가장 중요한 품질이라고 말하고 싶습니다. 간단한 문제는 깊이 생각해 보면 더 많은 것을 발견할 수 있다.
P09: 배낭 문제의 변화.
위에서 언급한 각종 배낭 문제는 모두 배낭용량 (비용) 제한 하에서 최대값을 얻을 것을 요구하지만, 배낭 문제에는 여러 가지 유연한 질문 방식이 있어 언급할 만하다. 하지만 배낭 문제가 최대값을 구하는 방법을 깊이 이해한다면, 문제 방법이 바뀌어도 알고리즘을 생각해 내는 것은 어렵지 않다고 생각한다.
예를 들어, 얼마나 많은 물건을 넣을 수 있는지, 얼마나 많은 배낭을 넣을 수 있는지 알아내십시오. 이는 특정 문제에 따라 이전 방정식을 사용하여 모든 상태 (F 배열) 의 값을 구할 수 있습니다.
또한 요구 사항이 "최소 합계" 및 "최소 총 개수" 인 경우 위의 상태 전환 방정식에서 max 를 min 으로 변경하기만 하면 됩니다.
여기에 좀 더 다양한 문제가 있다.
출력 시나리오
일반적으로 배낭 문제는 최적의 값이 필요합니다. 이 최적 값을 출력해야 하는 경우 일반적인 동적 계획 문제 출력 시나리오의 방법을 참조할 수 있습니다. 즉, 상태 전환 방정식의 어느 것이 각 상태의 최적 값인지, 즉 어느 정책에서 파생되었는지 기록합니다. 이 전략에 따라 이전 상태를 찾은 다음 이전 상태에서 앞으로 밀어낼 수 있습니다.
또는 0 1 배낭의 경우 방정식은 f[v]=max{f[v], f[v-c]+w} 입니다. 그런 다음 배열 g [v], g[v]=0 은 f[v] 의 값을 파생할 때 방정식의 이전 항목 (즉, f[v]=f[v]), g[v] 는 방정식을 채택한 다음 항목을 나타냅니다. 이 두 항목은 각각 두 가지 전략을 나타냅니다. 즉, 항목 I 는 선택되지 않고, 항목 I 는 선택됩니다. 그런 다음 출력 체계의 의사 코드를 다음과 같이 쓸 수 있습니다 (최종 상태를 f[N][V] 로 설정).
I=N
V=V
While(I & gt；; 0)
If(g[v]==0)
선택하지 않은 항목 I 인쇄
Else if(g[v]== 1)
"내 선택 항목" 을 인쇄합니다
V=v-c
또한 f[v] 값을 기준으로 방정식의 이전 또는 다음 항목을 실시간으로 찾을 수 있습니다. 즉, g 배열을 기록할 필요가 없습니다. 위 코드의 g [v]==0 은 F [v] = = F, g [v] = =/kk 로 변경됩니다
최소 출력 사전 순서를 가진 최적의 솔루션
여기서' 사전 순서가 가장 작다' 는 항목 1 의 선택 시나리오 이후 사전 순서가 가장 낮다는 것을 의미합니다 ... n 배열. 0 1 배낭 최소 사전 순서를 출력하는 방안을 예로 들어보겠습니다.
일반적으로 사전 순서가 가장 작은 최적의 방안을 찾으려면 이전 시 전략에만 주의하면 된다. 첫째, 하위 문제의 정의를 약간 변경해야합니다. 1 항목이 있는 최적의 방안이 있다면 대답은 1 항목을 포함해야 합니다. 원래 질문은 배낭 용량이 v-c[ 1] 이고 항목이 2 인 하위 질문으로 변환됩니다. 그러나 먼저 항목을 역순으로 배열하는 것이 더 쉬울 수 있으며, 다음은 항목이 이미 역순으로 배열된 사실에 따라 설명될 것이다.
이 경우 고전적인 상태 전이 방정식에 따라 평가할 수 있지만 n 에서 1 입력까지 f[v]==f 와 f[v]==f[f-c]+w 가 모두 있다는 점에 유의해야 합니다
방안의 총수를 찾아내다
배낭 문제의 경우 주어진 배낭 용량, 상품 비용 및 상품 간의 관계 (그룹화, 의존성 등) 입니다. ), 각 물품의 수치를 제시한 후 얻은 최대치 외에도 배낭을 가득 채우거나 배낭을 지정된 용량에 포장하는 방안의 총수를 얻을 수 있다.
이러한 문제의 경우 일반적으로 상태 전환 방정식의 max 를 sum 으로 변경하기만 하면 됩니다. 예를 들어, 각 항목이 0 1 배낭 중 하나인 경우 이전 방정식은 f[v]=sum{f[v], f[v-c]+w}, 초기 조건은 f [
사실, 가능한 이유는 상태 전이 방정식이 가능한 모든 배낭 구도 방안을 고찰했기 때문이다.
총 최적 시나리오 수
이곳의 최적 방안은 상품의 총가치가 가장 큰 방안을 가리킨다. 또는 0 1 배낭을 예로 들어 보겠습니다.
최대 총 가치와 총 시나리오 수를 찾는 아이디어를 결합하여 총 최적 솔루션 수를 다음과 같이 찾을 수 있습니다. f[v] 는 위의 의미와 동일합니다. g[v] 는 하위 문제에 대한 총 최적 솔루션 수를 나타내므로 g[v] 의 의사 코드는 f[v] 와 함께 계산됩니다.
I= 1 .. 보통
V=0..V 의 경우
F [v] = 최대 {f [v], f[v-c]+w}
G[v]=0
If(f[v]==f[v])
회사 (g[v], g[v]
If(f[v]==f[v-c]+w)
Inc(g[v], g[v-c])
만약 당신이 이런 문제를 처음 본다면 위의 위코드를 자세히 이해해 주세요.
요약
분명히, 배낭 동적 계획 문제의 모든 방법을 다 소진할 수는 없다. 배낭 동적 계획과 다른 분야 (예: 수론, 도론) 를 결합한 문제도 있다. 배낭 문제에 대한 이 주제 문장 에서는 논의되지 않는다. 하지만 앞서 언급한 모든 배낭 문제의 사고와 상태 전이 방정식을 깊이 이해하고 다른 변형 방법을 접하면 문제의 난이도가 NOIP 에 속하기만 하면 알고리즘을 생각해 내는 것은 어렵지 않을 것이다. (윌리엄 셰익스피어, Noip, Northern Exposure (미국 TV 드라마), 도전명언)
OIer 가 가져야 할 자질이어야 한다.