01 가방 이해 및 공간 최적화 (동적 기획)

디 렉 터 리:

문제 설명

문제 분석

구조 최 적 화

공간 최적화

1. 질문 설명: N 개의 아 이 템 과 용량 이 C 인 가방 을 지정 합 니 다. 각 아 이 템 의 무 게 는 Wi 이 고 가 치 는 Vi 입 니 다. 각 아 이 템 은 가방 에 넣 거나 가방 에 넣 지 않 는 것 만 선택 할 수 있 습 니 다.가방 을 불 러 올 수 있 는 총 가 치 를 어떻게 선택 하 시 겠 습 니까?
2. 문제 분석: 2 차원 배열 을 사용 하여 모든 상 태 를 저장 합 니 다.2 차원 배열 의 크기 는 m [n] [c] 이 고 그 중에서 m [i] [j] 는 앞의 i 개 아 이 템 에서 적당 한 선택 을 하여 가방 용량 j 를 초과 하지 않 을 때 최대 가 치 를 얻 을 수 있 음 을 나타 낸다.m [i] [j] 의 계산 방법 분석

case (1): j < w [i], 즉 가방 용량 이 j 일 경우 i 번 째 아 이 템 을 내 려 놓 을 수 없 으 며, 이때 이 아 이 템 을 불 러 오지 않 기로 선택 하 였 습 니 다.즉 m [i] [j] = m [i - 1] [j], 이 등식 은 i 번 째 아 이 템 을 직면 할 때 선택 하지 않 고 이 값 은 전 i - 1 개 아 이 템 을 선택 할 때 최대 가 치 를 나타 낸다.

case (2): j > = w [i], 즉 가방 의 용량 은 제 i 개 아 이 템 을 내 려 놓 을 수 있 지만 가 치 를 극 대화 하기 위해 아 이 템 i 를 가방 에 넣 을 지 여 부 를 고려 해 야 한다.가방 에 넣 으 면 m [i] [j] = m [i - 1] [j - w [i] + v [i], 그 중에서 m [i - 1] [j - w] 는 i - 1 개의 물품 을 고려 한 것 을 말 하 는데 가방 용량 이 j - w [i] 일 때의 가장 큰 가 치 는 본질 적 으로 i 개의 물품 에 w [i] 의 공간 을 비 운 것 이다.가방 에 넣 지 않 으 면 m [i] [j] = m [i - 1] [j].

위의 분석 에 따 르 면 상태 전이 방정식 을 얻 을 수 있다.

if(j >= w[i])：
    m[i][j] = max(m[i-1][j], m[i-1][j-w[i]] + v[i])
else：
    m[i][j] = m[i-1][j]

구현 코드:

for(int i=1;i<=n;i++)  // n     
    {
        for(int j=1;j<=c;j++)  // c      
        {
            if(j>=w[i])  //   
                m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); //    
 
 
            else //   
                m[i][j]=m[i-1][j];
        }
    }

위 에서 2 차원 배열 의 마지막 값 m [n] [c] 를 계산 하면 최대 가치 이다.
3. 구조 최 적 화 (앞에서 일 하면 가장 큰 가 치 를 얻 을 수 있 지만 어떤 물건 을 골 라 서 얻 은 최대 치 인지 모 르 겠 음)

사고: m [n] [c] 가 가장 좋 은 값 입 니 다. 만약 에 m [n] [c] = m [n - 1] [c] 가 n 번 째 물품 이 있 는 지 없 는 지 설명 하면 x [n] = 0;그렇지 않 으 면 x [n] = 1.x [n] = 0 일 때 x [n - 1] [c] 에서 계속 구 조 를 하 는 것 이 가장 좋 습 니 다.x [n] = 1 일 때 x [n - 1] [c - w [i] 에서 계속 구 조 를 하 는 것 이 가장 좋다.이런 식 으로 유추 하면 모든 최 적 화 를 구성 할 수 있다.

코드 구현:

void traceback()
{
    for(int i=n;i>1;i--)
    {
        if(m[i][c] == m[i-1][c])
            x[i] = 0;
        else
        {
            x[i] = 1;
            c -= w[i];
        }
    }
    x[1] = (m[1][c]>0) ? 1 : 0;
}

4. 공간 최적화

사고: 0 - 1 가방 의 상태 에서 방정식 을 옮 깁 니 다. m [i] [j] = max {m [i - 1] [j - w [i]] + v [i], m [i - 1] [j]} 의 특징 은 현재 상태 가 이전 상태의 잉여 용량 과 현재 물품 의 무게 v [i] 에 만 의존 하 는 관 계 를 알 고 있 습 니 다.이 특징 에 따라 우 리 는 m 를 1 차원 즉 m [j] = max {m [j], m [j - w [i] + v [i]} 로 낮 출 수 있다.이 방정식 에서 우 리 는 두 개의 m [j] 가 있 지만 구분 해 야 한 다 는 것 을 발견 할 수 있다.등호 왼쪽 의 m [j] 는 현재 i 의 상태 이 고 오른쪽 괄호 중의 m [j] 는 i - 1 상태 에서 의 값 입 니 다.

최적화 코드:

void FindMaxBetter()//          
{
    int i,j;
    for(i=1;i<=number;i++)
    {
        for(j=capacity;j>=0;j--)
        {
            if(B[j]<=B[j-w[i]]+v[i] && j-w[i]>=0 )//     
            {
                B[j]=B[j-w[i]]+v[i];
            }
        }
    }
}

비고: 최 적 화 된 코드 는 최대 가치 만 구 할 수 있 고 최 적 화 된 구 조 를 구성 할 수 없다 (즉, 어떤 물품 을 선택 하여 가 치 를 최대 화 했 는 지 모른다)

모 를 때 수 동 으로 한 번 밀어 보 는 것 이 가장 좋 은 방법 이다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Algorithms / 백준 2667번 파이썬

링크 풀이 코드 Algorithms / 백준 2667번 파이썬...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

01 가방 이해 및 공간 최적화 (동적 기획)

좋은 웹페이지 즐겨찾기