전단 및 알고리즘 - 동적 계획 의 01 가방 문제 에 대한 분석 및 구현

작년 에 업무 중의 한 응용 장면 때문에 동적 계획 을 사용 해 야 하기 때문에 가방 을 뜯 는 알고리즘 을 사용 하 는 데 시간 이 좀 걸 렸 다.
왜 작년 의 물건 을 올해 에 야 대충 썼 는 지 아마 게 으 른 가 보다
동적 계획 동적 프로 그래 밍
동적 계획 이 무엇 인지 간단히 말씀 드 리 겠 습 니 다.
위 키 피 디 아의 한 마디 를 인용 하면 복잡 한 문 제 를 비슷 한 여러 개의 키 문제 로 분해 한 다음 에 각 키 문 제 를 차례대로 해결 하 는 동시에 서브 문제 의 유사 성 때문에 계산 과정 에서 서브 문제 의 결 과 를 동시에 보존 하고 다음 에 똑 같은 서브 문 제 를 찾 으 면 된다.이렇게 하면 같은 문제 에 있어 서 다시 계산 시간 을 쓰 지 않 고 그 핵심 사상 은 바로 해체 와 기록 이다.
그렇다면 어떤 상황 에서 동적 계획 을 사용 할 수 있 습 니까?다음 과 같은 특징 을 갖 추어 야 한다.

가장 좋 은 서브 구 조 를 가진다. 만약 에 문제 의 가장 좋 은 해결 방안 이 가장 좋 은 서브 문제 의 해결 방안 을 통 해 얻 을 수 있다 면 이 문 제 는 가장 좋 은 서브 구조의 속성 이 있다. 간단 한 이 해 는 서브 문제 의 가장 좋 은 해석 으로 원 문 제 를 구성 하 는 가장 좋 은 해석

이다.

자 문 제 는 후 효성 이 없다. 즉, 자 문제 의 풀이 가 계산 되면 후속 적 인 자 문제 의 영향 을 받 아 변화 가 발생 하지 않 는 다

.

서브 문제 의 중첩 성, 즉 매번 발생 하 는 서브 문 제 는 새로운 문제 가 아니 라 앞의 서브 문 제 를 바탕 으로 변화 한 것 이기 때문에 서브 문제 간 에 중첩 성 을 가 져 야 한다. 이것 도 동태 계획 이 효율 적 인 원인

이다.
총 결 은 다음 과 같다.

가장 좋 은 구조 가 있다

하위 문제 찾기

'아래 에서 위로' 의 방식 으로 가장 좋 은 값 을 계산한다

계 산 된 정보 에서 가장 좋 은 경 로 를 구축 할 수 있다

가방 문제
먼저 한 장면 을 본다. 한 조 의 물품 을 정 하고 모든 물품 은 자신의 무게 와 가격 이 있다. 한 정 된 총 중량 에서 우 리 는 어떻게 선택해 야 물품 의 총 가격 을 가장 높 일 수 있 습 니까?
그렇다면 이런 문 제 를 해결 하기 위 한 알고리즘 을 가방 알고리즘 이 라 고 한다.
가방 문제 에 적용 되 는 장면 은 다음 과 같은 특징 을 가 져 야 한다.

고정 용량 의 가방 이 하나 있다

상품 은 두 가지 속성, 부피 와 가치

가 있 습 니 다.

가방 에 넣 을 수 있 는 최대 가치 또는 넣 을 수 있 는 구체 적 인 상품

구하 기
가방 문제 및 동적 계획
우 리 는 가방 의 용량 (v) 을 분해 하여 0 에서 v 까지 다른 가방 으로 나 눌 수 있 습 니 다. 그러면 문 제 는 용량 (0 - v) 의 가방 입 니 다. 우 리 는 해당 하 는 각 가방 이 수용 할 수 있 는 최대 가 치 를 계산 해 야 합 니 다. 똑똑 한 친구 들 은 이때 우리 가 소개 한 동적 계획 을 떠 올 렸 을 것 입 니 다. 맞습니다!가방 문제 의 가장 좋 은 해법 은 바로 동적 계획 으로 동적 계획 의 특징 에 완전히 부합된다.
가방 알고리즘 분류
가방 알고리즘 은 주로 세 가지 로 나 뉘 는데 다른 장면 은 이 세 가 지 를 바탕 으로 혼합 되 고 확장 된다.

01 가방, 아 이 템 당 1 개 만 있 으 며, 넣 거나 놓 지 않 기

를 선택 할 수 있 습 니 다.

완전 가방, 아 이 템 당 무한 개, 아 이 템 당 n 개

다 중 가방, 개 당 아 이 템 수량 제한

현재 01 가방 알고리즘 만 알 고 있 으 며 01 가방 알고리즘 만 소개 합 니 다.
01 가방
01 가방: N 개 아 이 템 과 V 용량 의 가방 이 있 습 니 다.모든 아 이 템 은 한 가지 만 있 습 니 다. 놓 거나 놓 지 않 을 수 있 습 니 다. 제 i 아 이 템 의 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 가 치 를 총화 할 수 있 는 지 알 아 보 세 요.
01 가방 문 제 는 가장 기본 적 인 가방 문제 로 가방 문제 에서 디자인 상태, 방정식 의 가장 기본 적 인 사상 을 포함한다. 또한 다른 유형의 가방 문 제 는 01 가방 문제 로 전환 하여 해결 할 수 있다.
알고리즘 의 핵심 은 상태 전이 방정식 이다. f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}이 방정식 을 어떻게 얻 었 는 지 에 대해 서 는 잠시 나의 능력 범 위 를 뛰 어 넘 었 습 니 다 ~ 동료 들 의 가르침 을 환영 합 니 다.
위의 방정식 을 설명 하 자 면 f[i][v] 앞의 i 개 물품 을 v 용량 의 가방 에 넣 으 면 얻 을 수 있 는 가장 큰 가 치 를 나타 낸다. 즉, 서브 문제 f[i][v] 의 해 를 계산 하 는 것 이다.
밤 을 들 면 번호 가 a, b, c, d, e 인 다섯 가지 물건 이 있 습 니 다. 그들의 무 게 는 각각 3, 6, 3, 8, 6 입 니 다. 그들의 가 치 는 각각 4, 6, 6, 12, 10 입 니 다. 지금 은 무게 가 10 인 가방 을 드 리 겠 습 니 다. 가방 에 담 긴 물건 이 가장 큰 가 치 를 가지 게 하 는 방법 입 니까?
상태 전이 방정식 에 따라 우 리 는 먼저 표를 만들어 서 하위 문제 의 해 를 관찰 하 는 데 사용한다.
name
weight
value
1
2
3
4
5
6
7
8
9
10
a
3
4
b
6
6
c
3
6
d
8
12
e
6
10
첫 번 째 단계, f[a][1] a 아 이 템 은 용량 이 1 인 가방 에 넣 고 최대 가 치 를 구 합 니 다. 설명 하기 편리 하도록 a1 칸 이 라 고 부 르 는데 놓 을 수 없 음 이 분명 합 니 다. 그러면 0 으로 풀 겠 습 니 다.
a2 단원 격 을 다시 계산 하면 방정식 f[a][2]=max{f[a-1][2],f[a-1][2-c[a]]+w[a]} = max{0,0} 에 따라 a2 = 0 을 얻 을 수 있다.
a3 를 더 계산 하면 방정식 f[a][3]=max{f[a-1][3],f[a-1][3-c[a]]+w[a]} = max{0,0+4} 에 따라 a3 = 4 를 얻 을 수 있다.
순서대로 a 줄 의 값 을 계산 하고, 이어서 b 줄 의 값 을 계산한다.f[b][1]=max{f[b-1][1],f[b-1][1-c[b]]+w[b]} = max{0,0+} b1 = 0 획득 가능f[b][3]=max{f[b-1][3],f[b-1][3-c[b]]+w[b]} = max{4,0} b1 = 4 획득 가능f[b][6]=max{f[b-1][6],f[b-1][6-c[b]]+w[b]} =max{f[a][6],f[a][6-6]+6} = max{4,0+6} b1 = 6f[b][9]=max{f[b-1][9],f[b-1][9-c[b]]+w[b]} =max{f[a][9],f[a][9-6]+6} = max{4,4+6} b1 = 10 획득 가능
시 계 를 가득 채 울 때 까지 차례대로 유추 하 다.
name
weight
value
1
2
3
4
5
6
7
8
9
10
a
3
4
0
0
4
4
4
4
4
4
4
4
b
6
6
0
0
4
4
4
6
6
6
10
10
c
3
6
0
0
6
6
6
10
10
10
12
12
d
8
12
0
0
6
6
6
10
10
12
12
12
e
6
10
0
0
6
6
6
10
10
12
16
16
그렇다면 용량 이 10 인 가방 의 최대 가 치 는 16 이라는 것 을 알 수 있다 면 해당 아 이 템 은?역 추적 법 을 통 해 해당 상품 을 찾 을 수 있 으 며 표 오른쪽 아래 부터 찾 을 수 있 습 니 다.
실례 설명 - 보너스 조합
장면
가장 좋 은 보너스 조합: 사용자 가 다음 에 결제 할 때 사용자 의 n 여 개의 보너스 중에서 사용자 에 게 가장 좋 은 보너스 조합 을 계산 하고 사용자 와 함께 사용 합 니 다. 보 너 스 는 두 가지 요소 가 있 습 니 다. 보너스 금액, 보너스 최저 사용 금액 입 니 다. 또한 조합의 보너스 중에서 가장 낮은 사용 금액 의 합 계 는 주문 금액 보다 크 면 안 됩 니 다.그렇다면 어떤 보너스 조합 이 가장 큰 혜택 일 까?이 문 제 는 한 마디 로 요약 하면:
아래 금액 W 에 따라 N 개의 보너스 중에서 하나 이상 의 보 너 스 를 선택 하여 현재 아래 금액 에서 가장 좋 은 보 너 스 를 계산 합 니 다.
문제 분석
이것 은 가방 문제 로 01 가방 의 특징 을 만족 시 키 고 주문 금액 을 가방 용량 으로 본다. 각 보 너 스 는 하나의 물품 이 고 물품 의 가 치 는 보너스 금액 이 며 물품 의 무 게 는 보너스 의 최저 적용 금액 이다. 서브 문 제 는 금액 (0 - w) 에 적용 되 는 가장 좋 은 보 너 스 를 구 하 는 조합 이다.
보너스 대상

{
    "amount": "39.00", //     -     
    "rangeBegin": "6000.00", //         -     
}

구체 적 인 코드 는 다음 과 같다.

/**
* @description
* 01    
* @private
* @param {any} dataList      
* @param {any} all     
* @returns 
*/
private knapsack(dataList, all) {
    const returnList = [];
    for (let i = 0; i < dataList.length; i++) {
        //       
        returnList[i] = [];
        for (let j = 0; j < all; j++) { //     
            const currentBagWeight = j + 1; //       
            const currentWeight = dataList[i].rangeBegin; //       
            const currentValue = dataList[i].amount; //      
            const lastW = currentBagWeight - currentWeight; //                     

            //        ，   
            let fV = lastW >= 0 ? currentValue : 0;
            fV = fV + (i > 0 && returnList[i - 1][lastW - 1] ? returnList[i - 1][lastW - 1] : 0);
            const nV = i > 0 && returnList[i - 1][j] ? returnList[i - 1][j] : 0;
            returnList[i][j] = Math.max(fV, nV);
        }
    }

    //     ，       
    let y = all - 1;
    const selectItem = [];
    let i = dataList.length - 1;

    while (i > -1) {
        if (returnList[i][y] === (returnList[i - 1] && returnList[i - 1][y - dataList[i].rangeBegin] || 0) + dataList[i].amount) {
            selectItem.push(dataList[i]);
            y -= dataList[i].rangeBegin;
        }
        i--;
    }

    return selectItem;
}

작은 매듭
누가 앞 에 개 라 고 하면 알고리즘 을 몰라 도 돼 ~ 하하 ~ 자신 에 게 제한 을 두 지 마 ~
참고 글 가방 문제 9 강 동적 계획 의 01 가방 문제