hdu 2844 Coins

전형적인 다중 가방 전환 01 가방과 다중 가방 문제

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int MAXN = 100010;
int dp[MAXN], n, m;
int AA[105];
// dp[i][j] = dp[i-1][j] || dp[i-1][j-w];
void oneBack(int w)
{
    for (int j = m; j >= w; --j)
        dp[j] = dp[j]||dp[j-w];
}
void comBack(int w)
{
    for (int j = w; j <= m; ++j)
        dp[j] = dp[j]||dp[j-w];
}
void solve()
{
    memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for (int i = 1; i<= n; ++i) scanf("%d", AA+i);
    for (int i = 1; i<= n; ++i)
    {
        int p, u;
        scanf("%d", &p);
        if (p*AA[i] >= m)
        {
            comBack(AA[i]);
            continue;
        }
        for (int o=1; o<=p; o<<=1)
        {
            u = o*AA[i];
            if (u <= m)
                oneBack(u);
            p -= o;
        }
        if (p > 0 && (u=p*AA[i]) <= m)
            oneBack(u);
    }
    int res = 0;
    for (int i = m; i>0; --i)
        res += dp[i];
    printf("%d
", res);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    while (scanf("%d%d", &n, &m)  && (n+m))
    {
        solve();
    }
    return 0;
}

hdu 1171 Big Event in HDU

만약에 배낭 문제라는 것을 한눈에 알 수 있다면 나머지는 틀을 씌우는 것이다. 이후에 비슷한 수조를 두 부분으로 나누고 차이가 가장 적은 문제를 만나면 참고할 수 있다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int MAXN = 1010;
int dp[5005*50], n, m;
int da[MAXN][2];
void oneBack(int w, int v)
{
    for (int j = m; j >= w; --j)
    {
        if (dp[j] < dp[j-w]+v)
            dp[j] = dp[j-w]+v;
    }
}
void comBack(int w, int v)
{
    for (int j = w; j <= m; ++j)
    {
        if (dp[j] < dp[j-w]+v)
            dp[j] = dp[j-w]+v;
    }
}
void solve()
{
    memset(dp, 0, sizeof dp);
    m = 0;
    for (int i = 1; i<= n; ++i)
        scanf("%d%d", &da[i][0], &da[i][1]),
              m += da[i][0]*da[i][1];
    int s = m;
    m /= 2;
    for (int i = 1; i<= n; ++i)
    {
        int p = da[i][0], a = da[i][1], u;
        if (p*a >= m)
        {
            comBack(p, p);
            continue;
        }
        for (int o=1; o<=a; o<<=1)
        {
            u = o*p;
            oneBack(u, u);
            a -= o;
        }
        if (a > 0 && (u=a*p) <= m)
            oneBack(u, u);
    }
    printf("%d %d
", s-dp[m], dp[m]);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    while (scanf("%d", &n)  && n>0)
    {
        solve();
    }
    return 0;
}

hdu 3591 The trouble of Xiaoqian

제목: 당신이 가지고 있는 동전의 액면가와 수량을 제시하고, 가게 주인은 같은 액면가를 가지고 수량에 제한이 없는 동전을 제공한다.이 동전으로 고정가치의 물건을 사면 주고 되찾는 동전의 총수가 가장 적다.가게 주인에게 주는 동전의 총액은 20000을 넘지 않는다.
m=min(200000, 모든 동전의 총가치) 설정
m<아이템 가치, 불가능
작업을 주고 되찾는 두 단계:
먼저 [0,m] 가치를 주는 동전에 필요한 최소 수량을 정방향으로 계산해 낸다.
dp[i][j] = min(dp[i-1][j], dp[i-1][j-w]+v);(다중 가방)
최종적으로 [0,m] 가치를 주는 동전에 필요한 최소 수량을 역산출한다.
dp[i][j] = min(dp[i-1][j], dp[i-1][j+w]+1)
dp[i][j] = min(dp[i][j], dp[i][j+w]+1)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int MAXN = 105, INF = 0x3f3f3f3f;
int n, t;
int V[MAXN], C[MAXN], dp0[20005];
void oneBack(int w, int v, int all)
{
    for (int j = all; j >= w; --j)
        dp0[j] = min(dp0[j], dp0[j-w]+v);
}
void comBack(int w, int v, int all)
{
    for (int j = w; j <= all; ++j)
        dp0[j] = min(dp0[j], dp0[j-w]+v);
}
void comBack_(int w, int v, int all)
{
    for (int j = all-w; j >= 0; --j)
        dp0[j] = min(dp0[j], dp0[j+w]+v);
}
void solve()
{
    memset(dp0, INF, sizeof dp0);
    dp0[0] = 0;
    int m = 0;
    for (int i = 1; i<= n; ++i)
        scanf("%d", V+i);
    for (int i = 1; i<= n; ++i)
        scanf("%d", C+i), m+=C[i]*V[i];
    m = min(20000, m);
    if (m < t)
    {
        printf("-1
");
        return;
    }
    // dp0[i][j] = min(dp0[i-1][j], dp0[i-1][j-w]+1); j==[0,m]
    for (int i = 1; i<= n; ++i)
    {
        int p = V[i], a = C[i], u;
        if (p*a >= m)
        {
            comBack(p, 1, m);
            continue;
        }
        for (int o=1; o<a; o<<=1)
        {
            u = o*p;
            oneBack(u, o, m);
            a -= o;
        }
        if ((u=a*p) <= m)
            oneBack(u, a, m);
    }
    dp0[0] = INF;
    for (int i = 1; i<= n; ++i)
    {
        comBack_(V[i], 1, m);
    }
    if (dp0[t] == INF)
        printf("-1
");
    else
        printf("%d
", dp0[t]);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int cs = 0;
    while (scanf("%d%d", &n, &t)  && (n+t))
    {
        printf("Case %d: ", ++cs);
        solve();
    }
    return 0;
}

hdu 1963 Investment

비교적 뚜렷한 다중 배낭 문제는 제목의 뜻을 따라오면 된다

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int MAXN = 45500;
int n, t, dp[MAXN], sm, m;
void comBack(int cost, int val, int all)
{
    for (int i = cost; i<= all; ++i)
        dp[i] = max(dp[i], dp[i-cost]+val);
}
int A[15], B[15];
// O(n) = 40*10*45500
void solve()
{
    int q;
    scanf("%d%d", &n, &m);
    scanf("%d", &q);
    for (int i = 0; i< q; ++i)
        scanf("%d%d", A+i, B+i);
    sm = n;
    while (m--)
    {
        memset(dp, 0, 4*(sm/1000+10));
        for (int i = 0; i< q; ++i)
            comBack(A[i]/1000, B[i], sm/1000);
        sm += dp[sm/1000];
    }
    printf("%d
", sm);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int t;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

hdu 3496 Watch The Movie

dp[n][m][l] = max(dp[n-1][m][l], dp[n-1][m-1][l-w]+v)
이 문제에는 몇 가지 주의점이 있다.
이미 n종의 영화 중 딱 m개를 선택했기 때문에 상태 이동은 전 상태가 m-1개에 도달할 수 있는지를 고려해야 한다
이 dp에서 l은 l보다 작다는 것을 표시하기 때문에 초기 상태에서 dp[0][0~l]를 0으로 설정한다(l로 표시가 딱 l이면 dp[0][0][0]]만 0으로 설정하고 최종 결과는 dp[n][m][0~l]에서 최대치를 취해야 한다)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int MAXN = 1002;
int dp[102][MAXN];
int n, m, l;
// dp[n][m][l] = max(dp[n-1][m][l], dp[n-1][m-1][l-w]+v)
void oneBack(int cost, int val)
{
    for (int j = m; j>0; --j)
        for (int i = l; i>= cost; --i)
            if (dp[j-1][i-cost]!=-1)
                dp[j][i] = max(dp[j][i], dp[j-1][i-cost]+val);
}
void solve()
{
    scanf("%d%d%d", &n, &m, &l);
    memset(dp, -1, sizeof dp);
    memset(dp[0], 0, 4*MAXN);
    for (int i = 0; i< n; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        oneBack(a, b);
    }
    printf("%d
", dp[m][l]==-1?0:dp[m][l]);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int t;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}