가방2016.5.1

제목

N 개 아이템과 V 가방 1개가 있습니다.
i번째 아이템을 넣는 데 소모되는 공간은 Ci이고, 얻는 가치는 Wi입니다.
어떤 아이템을 가방에 넣으면 가치 총합이 최대

2. 기본적인 사고방식

특징:
모든 물품은 하나뿐이니 놓든지 말든지 선택할 수 있다
하위 문제를 사용하여 상태를 정의하려면 다음과 같이 하십시오.
dp[i, V]는 앞의 i개 아이템을 용량이 v인 가방에 넣으면 얻을 수 있는 최대 가치를 나타낸다.
그러면 그 상태 이동 방정식은 다음과 같다. dp[i, V] = max{dp[i -3 1, V], dp[i -3 1, V -3 Ci] + Wi}
해석하다
"앞의 i개 아이템을 V 가방에 넣기"질문
i번째 아이템만 고려하는 전략(놓거나 놓지 않음)
그러면 전 i-3-1개 물품과 관련된 문제로 바뀔 수 있다
만약 i번째 아이템을 넣지 않는다면 문제는'전 i-3-1 아이템을 용량이 V인 가방에 넣기'로 바뀌고 가치는 dp[i-3-1, V]
i번째 아이템을 넣으면 문제는'앞의 i-3-1 아이템을 남은 용량의 V-3 Ci 가방에 넣기'로 바뀐다.
이때 얻을 수 있는 가장 큰 가치는 dp[i -3 1, V -3 C이다.
i] 여기에 i번째 아이템을 넣으면 얻을 수 있는 가치 W
i
POJ 3624 Charm Bracelet
//시간과 공간의 복잡성은 O(V * N)
//Result:MLE

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 3410;
int W[maxn];
int D[maxn];
int dp[maxn][12890];

int main()
{
//    freopen("in.txt", "r", stdin);
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i=1; i<=N; ++i) {
        scanf("%d%d", &W[i], &D[i]);
    }
    memset(dp, 0, sizeof(dp));
    for (int i=1; i<=N; ++i) {
        for (int j=1; j<W[i]; ++j) {
            dp[i][j] = dp[i-1][j];
        }
        for (int j=W[i]; j<=M; ++j) {
            dp[i][j] = max(dp[i-1][j-W[i]] + D[i], dp[i-1][j]);
        }
    }
    printf("%d
", dp[N][M]);
    return 0;
}

3. 공간 복잡도 최적화

이상의 방법의 시간과 공간 복잡도는 모두 O(V*N)이다. 그 중에서 시간 복잡도는 더 이상 최적화할 수 없지만 공간 복잡도는 O(V)로 최적화할 수 있다.
위의 기본적인 사고방식: 하나의 주순환 i=1...N, 매번 2차원 그룹 dp[i, 0.V]의 모든 값을 계산한다
그러면 만약에 하나의 수조 dp[0.V]만 사용한다면 i차 순환이 끝난 후 dp[V]에서 우리가 정의한 상태 dp[i,V]를 나타낼 수 있을까요?
dp[i, v]는 dp[i -3 1, v]와 dp[i -3 1, v -3 Ci] 두 개의 하위 문제가 점차 밀려왔다.
dp[i, v]를 추측할 때(즉 i차 주순환에서 dp[v]를 추측할 때) dp[i-3-1, v]와 dp[i-3-1, v-3]의 값을 사용할 수 있음을 보장할 수 있습니까?
사실상, 이것은 매번 주 순환에서 우리가 v=V..0의 체감 순서로 dp[v]를 계산하도록 요구한다
이렇게 해야만 dp[v]를 추측할 때 dp[v-3Ci]가 저장한 상태 dp[i-3-1, v-3Ci]의 값을 보장할 수 있다
POJ 3624 Charm Bracelet

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 3410;
int W[maxn];
int D[maxn];
int dp[12890];

int main()
{
//    freopen("in.txt", "r", stdin);
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i=1; i<=N; ++i) {
        scanf("%d%d", &W[i], &D[i]);
    }
    memset(dp, 0, sizeof(dp));
    for (int i=1; i<=N; ++i) {
        for (int j=M; j>=W[i]; --j) {
            if (dp[j-W[i]] + D[i] > dp[j]) {
                dp[j] = dp[j-W[i]] + D[i];
            }
        }
    }
    printf("%d
", dp[M]);
    return 0;
}

4. 초기화된 세부 문제

가장 잘 풀리는 배낭 문제 중에는 사실상 두 가지 그다지 같지 않은 문법이 있다
어떤 문제는'배낭을 꼭 채우라'고 요구했을 때 가장 잘 풀렸고, 어떤 문제는 반드시 등을 가득 채워야 한다고 요구하지 않았다.
이 두 가지 문법의 실현 방법은 초기화할 때 다소 다르다
만약 첫 번째 질문법이라면, 가방에 꼭 채워야 합니다.
그러면 초기화할 때 dp[0]가 0인 것을 제외하고 다른 dp[1.V]는 모두 -3-∞로 설정하면 최종적으로 얻은 dp[V]가 가방을 꼭 채우는 가장 좋은 방법이라는 것을 보장할 수 있다.
만약 반드시 등을 가득 채워야 한다고 요구하지 않았다면, 다만 가격이 될 수 있는 대로 크기를 바랄 뿐이다
초기화할 때 dp[0.V]를 모두 0으로 설정해야 합니다.
왜 그런 걸까요?다음과 같이 이해할 수 있습니다.
초기화된 F수 그룹은 사실 가방에 넣을 수 있는 아이템이 없을 때의 합법적인 상태입니다
가방이 꼭 채워져야 한다면, 이때 용량이 0인 가방만 아무것도 넣지 않고 가치가 0인 상황에서'꼭 채워야 한다'
기타 용량의 가방은 모두 합법적인 해가 없고 정의되지 않은 상태에 속하므로 -∞로 부여되어야 한다
만약 배낭이 반드시 가득 채워져야 하는 것이 아니라면, 어떤 용량의 배낭도 모두 합법적으로 '아무것도 넣지 않는다' 라고 풀 수 있다
이 해의 가치는 0이기 때문에 초기 상태의 값도 모두 0이다

다섯, 소결

01 가방 문제는 가장 기본적인 가방 문제
그것은 배낭 문제 중 설계 상태, 방정식의 가장 기본적인 사상을 포함하고 있다
또한, 다른 유형의 가방 문제도 01 가방 문제로 변환하여 해답을 구할 수 있다
그러므로 상기 기본적인 사고방식의 도출 방법, 상태 이동 방정식의 의미, 그리고 공간의 복잡도가 어떻게 최적화되는지 반드시 자세하게 체득해야 한다.
<가방 9강 V 2.0>%%% 저자, 작가에게 감사
HDU 2602 Bone Collector

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;

const int maxn = 100 + 10;
double Pj[maxn];
int Mj[maxn];
double dp[10010];

int main()
{
#ifdef __AiR_H
    freopen("in.txt", "r", stdin);
#endif // __AiR_H
    int T;
    while (scanf("%d", &T) != EOF) {
        while (T--) {
            double P;
            int N;
            int sum = 0;
            scanf("%lf%d", &P, &N);
            for (int i = 1; i <= N; ++i) {
                scanf("%d%lf", &Mj[i], &Pj[i]);
                sum += Mj[i];
            }
            memset(dp, 0, sizeof(dp));
            dp[0] = 1;
            for (int i = 1; i <= N; ++i) {
                for (int j = sum; j >= Mj[i]; --j) {
                    dp[j] = max(dp[j], dp[j - Mj[i]] * (1 - Pj[i]));
                }
            }
            for (int i = sum; i >= 0; --i) {
                if (dp[i] >= (1-P)){
                    printf("%d
", i);
                    break;
                }
            }
        }
    }
    return 0;
}

HDU 2546 식사 카드
문제 해결 방법:
마지막으로 가장 비싼 요리를 사자(여러 개 있을 수 있다)
그리고 브이=m-5를 구하고 첫 번째 비싼 음식을 고려하지 않는 01배낭 문제

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 1000 + 10;
int price[maxn];
int dp[1010];

int main()
{
#ifdef __AiR_H
    freopen("in.txt", "r", stdin);
#endif // __AiR_H
    int n;
    while (scanf("%d", &n) != EOF && n != 0) {
        int Max;
        int t;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &price[i]);
            if (i == 1) {
                Max = price[i];
                t = 1;
            } else if (price[i] > Max) {
                Max = price[i];
                t = i;
            }
        }
        int m;
        scanf("%d", &m);
        if (m < 5) {
            printf("%d
", m);
        } else {
            memset(dp, 0, sizeof(dp));
            for (int i = 1; i <= n; ++i) {
                if (i != t) {
                    for (int j = m-5; j >= price[i]; --j) {
                        dp[j] = max(dp[j], dp[j-price[i]] + price[i]);
                    }
                }
            }
            printf("%d
", m-dp[m-5]-Max);
        }
    }
    return 0;
}

HDU 1171 Big Event in HDU
V=halves로 전환 01 가방 문제

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 50 + 10;
int V[maxn];
int M[maxn];
int dp[130000];

int main()
{
#ifdef __AiR_H
    freopen("in.txt", "r", stdin);
#endif // __AiR_H
    int N;
    while (scanf("%d", &N) != EOF && N >= 0) {
        int sum = 0;
        for (int i = 1; i <= N; ++i) {
            scanf("%d%d", &V[i], &M[i]);
            sum += (V[i] * M[i]);
        }
        int halves = sum / 2;
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= N; ++i) {
            for (int j = 0; j < M[i]; ++j) {
                for (int k = halves; k >= V[i]; --k) {
                    dp[k] = max(dp[k], dp[k-V[i]] + V[i]);
                }
            }
        }
        printf("%d %d
", sum-dp[halves], dp[halves]);
    }
    return 0;
}