가방 문제 시리즈 튜 토리 얼 (1): 01 가방 문제

01 가방 문제
제목.
N 개의 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 물품 의 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 가 치 를 총화 할 수 있 는 지 알 아 보 세 요.
기본 적 인 사고방식
이것 은 가장 기본 적 인 가방 문제 로 모든 아 이 템 이 하나 밖 에 없 으 므 로 놓 거나 놓 지 않 는 것 을 선택 할 수 있 는 것 이 특징 이다.
하위 문제 로 상 태 를 정의 합 니 다: 즉 f [i] [v] 는 앞의 i 개 아 이 템 을 v 용량 의 가방 에 넣 으 면 얻 을 수 있 는 최대 가 치 를 표시 합 니 다.상태 전이 방정식 은:
4. 567913. 이 방정식 은 매우 중요 하 다. 기본적으로 가방 과 관련 된 모든 문제 의 방정식 은 이 방정식 에서 파생 된 것 이다.따라서 이 를 상세 하 게 설명 할 필요 가 있다. "앞의 i 개 물품 을 v 용량 의 가방 에 넣는다" 는 문 제 는 i 개 물품 의 전략 (놓 거나 놓 지 않 는 다) 만 고려 하면 앞의 i - 1 개 물품 과 관련 된 문제 로 바 뀔 수 있다.만약 에 i 번 째 아 이 템 을 넣 지 않 으 면 문 제 는 '전 i - 1 개 아 이 템 을 v 용량 의 가방 에 넣 습 니 다' 로 바 뀌 고 가 치 는 f [i - 1] [v] 입 니 다.i 번 째 아 이 템 을 넣 으 면 문 제 는 '앞의 i - 1 아 이 템 을 남 은 용량 v - c [i] 의 가방 에 넣 기' 로 바 뀌 는데 이때 얻 을 수 있 는 가장 큰 가 치 는 f [i - 1] [v - c [i]] 와 i 번 째 아 이 템 을 넣 어 얻 을 수 있 는 가치 w [i] 이다.
공간 복잡 도 최적화
상기 방법의 시간 과 공간 복잡 도 는 모두 O (VN) 인 데 그 중에서 시간 복잡 도 는 더 이상 최적화 할 수 없 을 것 이다. 그러나 공간 복잡 도 는 O (V) 까지 최적화 할 수 있다.
먼저 위 에서 말 한 기본 적 인 사고방식 이 어떻게 실현 되 는 지 를 고려 하면 틀림없이 주 순환 i = 1.. N 이 있 을 것 이다. 매번 2 차원 수조 f [i] [0.. V] 의 모든 값 을 계산한다.그렇다면 하나의 배열 f [0. V] 만 사용 하면 i 차 순환 이 끝 난 후에 f [v] 에서 우리 가 정의 한 상태 f [i] [v] 를 나타 내 는 것 을 보증 할 수 있 습 니까?f [i] [v] 는 f [i - 1] [v] 와 f [i - 1] [v - c [i] 두 가지 문제 가 밀 려 왔 습 니 다. f [i] [v] 를 밀 때 (즉, i 차 메 인 순환 에서 f [v] 를 밀 때) f [i - 1] [v] 와 f [i - 1] [v - c [i]] 의 값 을 얻 을 수 있 습 니까?사실, 이것 은 매번 메 인 순환 에서 우 리 는 v = V. 0 의 순서 로 f [v] 를 밀어 야 f [v] 를 밀 때 f [v - c [i] 가 상태 f [i - 1] [v - c [i] 의 값 을 저장 할 수 있 습 니 다.의사 코드 는 다음 과 같 습 니 다:
4. 567913. 그 중의 f [v] = max {f [v], f [v - c [i]} 한 마디 는 바로 우리 의 전이 방정식 f [i] [v] = max {f [i - 1] [v], f [i - 1] [v - c [i]} 에 해당 한다. 왜냐하면 현재 의 f [v - c [i] 는 원래 의 f [i - 1] [v - c [i]] 에 해당 하기 때문이다.v 의 순환 순 서 를 위의 역순 에서 순서 로 바 꾸 면 f [i] [v] 는 f [i] [v - c [i] 로 추정 되 며, 본제 와 뜻 이 맞지 않 지만, 또 다른 중요 한 가방 문제 입 니 다.
P02 가장 간편 한 해결 방안 이 므 로 1 차원 배열 로 만 01 가방 문 제 를 해결 하 는 것 이 필요 합 니 다.
사실 1 차원 배열 로 01 가방 을 풀 어 주 는 프로그램 은 뒤에서 여러 번 사용 되 기 때문에 01 가방 에 있 는 물건 을 처리 하 는 과정 을 추상 화하 고 이후 코드 에서 직접 호출 하여 설명 하지 않 습 니 다.
프로 세 스 제로 원 팩 은 01 가방 에 있 는 아 이 템 을 처리 하 는 것 을 나타 내 고 두 개의 매개 변수 cost, weight 는 각각 이 아 이 템 의 비용 과 가 치 를 나타 낸다.

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

이 과정 에서 의 처 리 는 앞에서 제시 한 의사 코드 와 다 릅 니 다.앞의 예제 프로그램 이 v = V. 0 으로 쓴 것 은 프로그램 에서 모든 상 태 를 방정식 에 따라 풀 고 불필요 한 사고 복잡 도 를 피하 기 위해 서 이다.여기 서 블랙박스 로 추상 화 된 과정 이 니 최 적 화 를 넣 을 수 있다.비용 이 cost 인 물품 은 상태 f [0. cost - 1] 에 영향 을 주지 않 는 다 는 것 은 분명 하 다.
이 과정 이 있 으 면 01 가방 문제 의 위조 코드 는 이렇게 쓸 수 있다.

for i=1..N
    for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]};

질문
우리 가 본 최 적 화 를 구 하 는 가방 문제 중 에는 사실상 두 가지 서로 다른 질문 이 있다.어떤 문 제 는 '마침 가방 을 가득 채 워 라' 는 최 적 화 를 요구 하고, 어떤 문 제 는 반드시 가방 을 가득 채 워 야 한다 고 요구 하지 않 았 다.이 두 가지 질문 법 을 구별 하 는 실현 방법 은 초기 화 할 때 다르다.
만약 에 첫 번 째 질문 법 이 라면 가방 을 꽉 채 워 야 한다. 그러면 초기 화 할 때 f [0] 을 제외 하고 다른 f [1. V] 를 모두 - 표시 로 설정 하면 최종 적 으로 얻 은 f [N] 이 가방 을 꽉 채 우 는 가장 좋 은 방법 임 을 보증 할 수 있다.
등 을 가득 채 워 야 한 다 는 요구 가 아니 라 가격 이 최대한 비 싸 기 를 원한 다 면 초기 화 할 때 f [0. V] 를 모두 0 으로 설정 해 야 한다.
왜 일 까요?이렇게 이해 할 수 있 습 니 다. 초기 화 된 f 배열 은 사실상 가방 에 넣 을 수 있 는 아 이 템 이 없 을 때 합 법 적 인 상태 입 니 다.만약 에 가방 을 적당 하 게 채 워 달라 고 요구한다 면 이때 용량 이 0 인 가방 만 0 인 nothing 에 의 해 '적당 하 게 채 워 진다' 고 할 수 있 고 다른 용량 의 가방 은 모두 합 법 적 인 해석 이 없고 정의 되 지 않 은 상태 에 속 하 며 그들의 수 치 는 모두 - 표시 되 어야 한다.만약 에 가방 이 반드시 가득 채 워 져 야 하 는 것 이 아니라면 모든 용량 의 가방 은 합 법 적 으로 '아무것도 담 지 않 습 니 다' 를 풀 수 있 습 니 다. 이 분해 의 가 치 는 0 이기 때문에 초기 상태의 값 도 모두 0 입 니 다.
이 작은 기 교 는 다른 유형의 가방 문제 에 충분히 보급 할 수 있 고 그 다음 에 상태 이전 전의 초기 화 에 대해 설명 하지 않 습 니 다.
상수 최적화
앞의 의사 코드 에는 for v = V. 1 이 있 습 니 다. 이 순환 의 하한 선 을 개선 할 수 있 습 니 다.
마지막 f [v] 의 값 만 필요 하기 때문에 이전 아 이 템 을 거꾸로 미 루 면 사실은 f [v - w [n] 만 알 면 됩 니 다.이런 식 으로 미 루 면 제 이 제 이 가방 은 f [v - sum {w [j. n]} 만 알 면 됩 니 다. 즉, 코드 에 있 는 것 입 니 다.

procedureZeroOnePack(cost,weight)
    for v=V..cost
        f[v]=max{f[v],f[v-cost]+weight}

되다

for i=1..N
    ZeroOnePack(c[i],w[i]);

이것 은 V 가 비교적 클 때 유용 하 다.
작은 매듭
01 가방 문 제 는 가장 기본 적 인 가방 문제 로 가방 문제 에서 디자인 상태, 방정식 의 가장 기본 적 인 사상 을 포함한다. 또한 다른 유형의 가방 문 제 는 01 가방 문제 로 전환 하여 해결 할 수 있다.그러므로 반드시 위의 기본 적 인 사고방식 의 얻어 지 는 방법, 상태 전이 방정식 의 의미, 그리고 마지막 에 어떻게 최 적 화 된 공간 복잡 도 를 자세히 체득 해 야 한다.