요약 - 01 가방 문제 (동적 계획 알고리즘)

0 - 1 가방 문제: n 가지 물품 과 용량 이 C 인 가방 을 정 하고 물품 i 의 무 게 는 wi 이 며 그 가 치 는 vi 이다.
― 가방 에 들 어 가 는 아 이 템 을 어떻게 선택해 야 가방 에 들 어 가 는 아 이 템 의 총 가치 가 가장 큽 니까?
한 파 를 분석 하면 모든 물품 에 대해 우 리 는 두 가지 선택 을 선택 하거나 가 져 오지 않 을 뿐 특정한 물품 의 일부분 을 선택 할 수 없고 같은 물품 을 여러 번 불 러 올 수 없다.
해결 방법: 크기 를 설명 합 니 다. m [n] [c] 의 2 차원 배열, m [i] [j] 는 제 i 물품 을 직면 하고 있 으 며 가방 용량 은? j 시 얻 을 수 있 는 최대 가치 ，그러면 우 리 는 m [i] [j] 의 계산 방법 을 쉽게 분석 할 수 있다.
(1). j < w [i] 의 경우 가방 용량 이 부족 하여 제 i 아 이 템 을 내 려 놓 을 수 있 습 니 다. 가지 지 않 기로 선택 할 수 밖 에 없습니다.
m[ i ][ j ] = m[ i-1 ][ j ]
(2). j > = w [i] 의 경우 가방 용량 이 i 번 째 아 이 템 을 내 려 놓 을 수 있 습 니 다. 이 아 이 템 을 가지 고 더 큰 가 치 를 얻 을 수 있 는 지 고려 해 야 합 니 다.
가 져 가면 m [i] [j] = m [i - 1] [j - w [i] + v [i].여기 m [i - 1] [j - w [i] 는 i - 1 개의 아 이 템 을 고려 한 것 으로 가방 용량 이 j - w [i] 일 때의 최대 가치 이자 i 번 째 아 이 템 에 w [i] 의 공간 을 비 운 셈 이다.
안 들 면 m [i] [j] = m [i - 1] [j], 동일 (1)
가 져 갈 지 말 지 는 당연히 이 두 가지 상황 을 비교 하 는 것 이 가장 가치 가 있다.
이로부터 상태 전이 방정식 을 얻 을 수 있다.

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];

예: 0 - 1 가방 문제.동적 계획 알고리즘 을 사용 하여 0 - 1 가방 문 제 를 풀 때 2 차원 배열 m [i] [j] 를 사용 하여 가방 의 남 은 용량 을 j 로 저장 하고 선택 할 수 있 는 아 이 템 은 i, i + 1,..., n 시 0 - 1 가방 문제 의 가장 좋 은 값 입 니 다.그리 기
가치 배열 v = {8, 10, 6, 3, 7, 2},
중량 배열 w = {4, 6, 2, 2, 5, 1},
가방 용량 C = 12 시 대응 m [i] [j] 배열.
0
1
2
3
4
5
6
7
8
9
10
11
12
1
0
0
0
8
8
8
8
8
8
8
8
8
2
0
0
0
8
8
10
10
10
10
18
18
18
3
0
6
6
8
8
14
14
16
16
18
18
24
4
0
6
6
9
9
14
14
17
17
19
19
24
5
0
6
6
9
9
14
14
17
17
19
21
24
6
2
6
8
9
11
14
16
17
19
19
21
24
(첫 줄 과 첫 번 째 열 은 번호 이 고 그 수 치 는 0 이다)
예 를 들 어 m [2] [6], 두 번 째 아 이 템 에 대해 가방 용량 이 6 일 때 우 리 는 가지 지 않 는 것 을 선택 할 수 있 습 니 다. 그러면 가 치 를 얻 는 것 은 첫 번 째 아 이 템 의 가치 8 입 니 다. 가 져 오 면 첫 번 째 아 이 템 을 꺼 내 고 두 번 째 아 이 템 을 넣 어야 합 니 다. 가치 10 이면 우 리 는 당연히 가 져 가 는 것 을 선택 합 니 다.m[2][6]=m[1][0]+10=0+10=10;순서대로 유추 하여 m [6] [12] 를 얻 는 것 은 모든 물품 을 고려 하 는 것 이 고 가방 용량 이 C 일 때의 가장 큰 가치 이다.

#include 
#include 
using namespace std;


const int N=15;


int main()
{
    int v[N]={0,8,10,6,3,7,2};
    int w[N]={0,4,6,2,2,5,1};


    int m[N][N];
    int n=6,c=12;
    memset(m,0,sizeof(m));
    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];
        }
    }


    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=c;j++)
        {
            cout<

이 단계 에 이 르 러 얻 을 수 있 는 가장 큰 가 치 를 확정 할 수 있 지만, 우 리 는 어떤 물건 을 선택 하면 가장 큰 가 치 를 얻 을 수 있 는 지 구체 적 으로 알 지 못 한다.
다른 x [] 배열, x [i] = 0 은 들 지 않 는 다 는 뜻 이 고 x [i] = 1 은 들 지 않 는 다 는 뜻 이다.
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;
}

예:
한 공장 은 내년 에 A, B, C, D 네 개의 신축 프로젝트 가 있 을 것 으로 예상 하고 있 으 며, 각 프로젝트 의 투자 액 인 Wk 와 그 투자 후의 수익 Vk 는 다음 표 와 같이 투자 총액 이 30 만 위안 인 데, 어떻게 프로젝트 를 선택해 야 총 수익 을 최대 로 할 수 있 습 니까?
Project
Wk
Vk
A
15
12
B
10
8
C
12
9
D
8
5
앞의 두 단락 코드 를 결합 하 다

#include 
#include 
using namespace std;

const int N=150;

int v[N]={0,12,8,9,5};
int w[N]={0,15,10,12,8};
int x[N];
int m[N][N];
int c=30;
int n=4;
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;
}

int main()
{


    memset(m,0,sizeof(m));
    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];
        }
    }/*
    for(int i=1;i<=6;i++)
    {
        for(int j=1;j<=c;j++)
        {
            cout<

출력 x [i] 배열: 0111, 출력 m [4] [30]: 22.
결론: BCD 세 항목 을 선택 하면 총 수익 이 22 만 위안 으로 가장 크다.
그러나 이런 알고리즘 은 한 가지 최 적 화 를 얻 을 수 있 을 뿐 모든 최 적 화 를 얻 을 수 없다.