동적 계획 의 가방 문제

가방 문제
N 개의 아 이 템 과 V 용량 의 가방 이 있 습 니 다. i 번 째 아 이 템 의 부 피 는 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 가 치 를 총화 할 수 있 는 지 알 아 보 세 요.
상태 전이 방정식: f [i] [v] = max (f [i - 1] [v], f [i - 1] [v - c [i]] + w [i]) 이 방정식 은 매우 중요 하 다. 기본적으로 가방 과 관련 된 모든 문제 의 방정식 은 이 방정식 에서 파생 된 위조 코드 는 다음 과 같다.

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

i 번 째 아 이 템 을 넣 지 않 으 면 문 제 는 '전 i - 1 개 아 이 템 을 v 용량 의 가방 에 넣 는 것' 으로 바 뀌 고 가 치 는 f [i - 1] [v] 이다.첫 번 째 아 이 템 을 넣 으 면 문 제 는 '전 i - 1 개 아 이 템 을 남 은 용량 v - c [i] 의 가방 에 넣 는 것' 으로 바 뀌 었 다. 이때 얻 을 수 있 는 가장 큰 가 치 는 f [i - 1] [v - c [i]] 에 두 번 째 아 이 템 을 넣 어 얻 을 수 있 는 가치 w [i] 다.
예제
설명 천진 은 타고 난 자질 이 총명 한 아이 로 그의 꿈 은 세계 에서 가장 위대 한 의사 가 되 는 것 이다.이 를 위해, 그 는 부근 에서 가장 명망 있 는 의 사 를 스승 으로 모 시 려 고 한다.의 사 는 그의 자질 을 판단 하기 위해 그 에 게 어 려 운 문 제 를 냈 다.의 사 는 그 를 약초 가 가득 한 동굴 로 데 리 고 가서 그 에 게 말 했다."얘 야, 이 동굴 에 다른 약초 들 이 있어. 한 포기 한 포기 따 는 데 시간 이 걸 리 고, 한 포기 에 도 가치 가 있어. 내 가 시간 을 줄 게. 그 동안 약 초 를 캐 도 돼. 똑똑 한 아이 라면 약초 의 총가치 가 가장 클 거 야."만약 당신 이 진진 이 라면, 당신 은 이 임 무 를 완성 할 수 있 습 니까?
입력 의 첫 줄 은 두 개의 정수 T (1 < = T < = 1000) 와 M (1 < = M < = 100) 로 나 뉘 어 져 있 으 며, 하나의 빈 칸 으로 나 누 어 져 있 으 며, T 는 약 초 를 채취 할 수 있 는 시간 을 나타 내 고, M 은 동굴 의 약초 수 를 나타 낸다. 다음 M 줄 은 1 에서 100 사이 (1 과 100 포함) 의 정수 두 개 를 포함 하여 각각 어떤 약 초 를 채취 하 는 시간 과 이 약초 의 가 치 를 나타 낸다.
출력 출력 은 한 줄 을 포함 합 니 다. 이 줄 은 하나의 정수 만 포함 하고 정 해진 시간 내 에 채취 할 수 있 는 약초 의 최대 총 가 치 를 표시 합 니 다.
Sample Input

70 3
71 100
69 1
1 2

Sample Output

3

문제 풀이 코드 1

#include <iostream>
using namespace std;

int main()
{
    int T, M;
    cin>>T>>M;
    int c[101] = {0};
    int w[101] = {0};
    for (int i = 1; i <= M; i++)
    {
        cin>>w[i]>>c[i];
    }

    int **f = new int*[M + 1];
    for (int i = 0; i <= M; i++)
    {
        f[i] = new int[T + 1];
    }

    //     0
    for (int i = 0; i <= M; i++)
    {
        f[i][0] = 0;
    }

    //     0
    for (int i = 0; i <= T; i++)
    {
        f[0][i] = 0;
    }

    int i, j;
    for (i = 1; i <= M; i++)
    {
        for (j = 1; j <= T; j++)
        {
            if (j >= w[i])
            {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + c[i]);
            }
            else
            {
                f[i][j] = f[i - 1][j];
            }

        }
    }
    cout<<f[i-1][j-1]<<endl;
    //cout<<f[M][T]<<endl;

    for (int i = 0; i <= M; i++)
    {
        delete [] f[i];
    }
    delete [] f;

    return 0;
}

문제 풀이 코드 2

#include <iostream>
using namespace std;

int main()
{
    int T, M;
    cin>>T>>M;
    int c[101] = {0};
    int w[101] = {0};
    for (int i = 1; i <= M; i++)
    {
        cin>>w[i]>>c[i];
    }

    int f[1001][101] = {0};

    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= T; j++)
        {
            if (j >= w[i])
            {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + c[i]);
            }
            else
            {
                f[i][j] = f[i - 1][j];
            }
        }
    }
    cout<<f[M][T]<<endl;

    return 0;
}

코드 2 는 공간 을 많이 소모 하지만 코드 는 매우 간결 할 수 있다.
문제 풀이 코드 3
1 차원 배열 을 사용 하여 이 문 제 를 해결 할 수 있 지만 주의해 야 할 것 은 메모리 순환 의 순 서 는 반드시 V. 0 이 어야 한 다 는 것 이다. 즉,:

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

내부 순환 이 0.. V 이면 실제 상태 방정식 은 f [i] [v] = max (f [i - 1] [v], f [i] [v - c [i]] + w [i]) 이다.

#include <iostream>
using namespace std;

int main()
{
    int T, M;
    cin>>T>>M;
    int c[101] = {0};
    int w[101] = {0};
    for (int i = 1; i <= M; i++)
    {
        cin>>w[i]>>c[i];
    }

    int f[101] = {0};
    for (int i = 1; i <= M; i++)
    {
        for (int j = T; j >= 1; j--)
        {
            if (j >= w[i])
            {
                f[j] = max(f[j], f[j - w[i]] + c[i]);
            }
        }
    }
    cout<<f[T]<<endl;

    return 0;
}