01 가방

01 가방
0 - 1 가방 문제: n 가지 물품 과 용량 이 C 인 가방 을 정 하고 물품 i 의 무 게 는 wi 이 며 그 가 치 는 vi 이다.
― 가방 에 들 어 가 는 아 이 템 을 어떻게 선택해 야 가방 에 들 어 가 는 아 이 템 의 총 가치 가 가장 큽 니까?
더욱 구체 적 인 추상 적 인 문 제 는 다음 과 같다.
n 개의 옵션 이 있 고 가 치 는 vi 이 며 소모 와 이 는 총 소모 가 C 인 상황 에서 선택 하여 총 가치 가 가장 크다.
dpi] [j] 를 사용 하면 i 번 째 옵션 을 선택 할 수 있 는 최대 값 을 사용 할 수 있 음 을 표시 합 니 다. 현재 옵션 을 선택 하거나, 현재 옵션 을 선택 하지 않 거나, 현재 옵션 을 선택 하지 않 거나: d p [i] [i] [j] = {d p [i - 1] [j], j < w i m a x (d p [i] [j − i] + v i, d p [i - 1] [i] [i]] [j]] [j] j] = [j] = w p [i] [i]]] [j] [i]]]] [j]]]] [j p [i p [i]] j]]]]]]] j = w i p [i p [i p [i]]]] [j]]]]] [j]] j] ={dp [i - 1] [j], max (dp [i] [j - wi] + vi, dp [i - 1] [j]) j < wij > = wi 는 아래 에서 위로 옮 겨 다 니 며 먼저 물건 을 옮 겨 다 니 고 비용 을 소모 하 는 것 은 먼저 바 텀 아 이 템, 저 용량 의 기록 을 기록 한 것 과 같 으 며 꼭대기 층 은 기록 을 알 고 있 기 때문에 빠 른 판단 을 할 수 있다.

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=c;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];
        }
    }

주의해 야 할 것 은 모든 동 귀 실현 시 경계 조건 과 바 텀 조건 의 설정 에 주의해 야 하고 반드시 공식 적 인 의미 에 부합 해 야 한 다 는 것 이다.
최대 가 치 를 얻 을 수 있 는 선택 항목 을 확인 합 니 다.
다른 x [] 배열, x [i] = 0 은 안 가 져 가 겠 다 고 표시 하고 x [i] = 1 은 가 져 가 겠 다 고 표시 한다.

    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;//        ，