51Nod－1086－背包问题 V2

描述

题解

这里提供三种代码，前两种方法一致，复杂度O(V*Σlog n[i])，不同的是，第二个是模版；第三种代码最优，复杂度为O(VN)，可惜十分不好理解，具体推导过程不再赘述，有些懵懵懂懂……

这个问题是一道常见的多重背包问题，和完全背包相似，可以转化为01背包问题，但是转化过程中，不能简单的将第i种拆分成ci[i]个物品，要利用一些数学知识来优化，应拆分为1、2、4……c[i]-sum种，sum为前边拆分的和。

代码

One：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 110;
const int MAXW = 5e4 + 10;
const int base[] = {
  1, 2, 4, 8, 16, 32, 64, 128};
const int bases[] = {
  1, 3, 7, 15, 31, 63, 127, 255};
const int MAXP = 8; // 最多分为8份

int Wi[MAXN * 8];
int Pi[MAXN * 8];
int dp[MAXW];

int main(int argc, const char * argv[])
{
    freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    int N, W;
    cin >> N >> W;

    int key = 1;
    int wi, pi, ci;
    for (int i = 1; i <= N; i++)
    {
        scanf("%d %d %d", &wi, &pi, &ci);
        for (int i = 0; i < MAXP; i++)
        {
            if (bases[i] > ci)
            {
                Wi[key] = wi * (ci - bases[i - 1]);
                Pi[key++] = pi * (ci - bases[i - 1]);
                break;
            }
            else
            {
                Wi[key] = wi * base[i];
                Pi[key++] = pi * base[i];
            }
            if (bases[i] == ci)
            {
                break;
            }
        }
    }

    for (int i = 1; i < key; i++)
    {
        for (int j = W; j >= Wi[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - Wi[i]] + Pi[i]);
        }
    }

    std::cout << dp[W] << '\n';
    return 0;
}

Two：

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 101;
const int SIZE = 50001;

int dp[SIZE];
int volume[MAXN], value[MAXN], c[MAXN];
int n, v;           // 总物品数，背包容量

// 01背包
void ZeroOnepark(int val, int vol)
{
    for (int j = v ; j >= vol; j--)
    {
        dp[j] = max(dp[j], dp[j - vol] + val);
    }
}

// 完全背包
void Completepark(int val, int vol)
{
    for (int j = vol; j <= v; j++)
    {
        dp[j] = max(dp[j], dp[j - vol] + val);
    }
}

// 多重背包
void Multiplepark(int val, int vol, int amount)
{
    if (vol * amount >= v)
    {
        Completepark(val, vol);
    }
    else
    {
        int k = 1;
        while (k < amount)
        {
            ZeroOnepark(k * val, k * vol);
            amount -= k;
            k <<= 1;
        }
        if (amount > 0)
        {
            ZeroOnepark(amount * val, amount * vol);
        }
    }
}

int main()
{
    while (cin >> n >> v)
    {
        for (int i = 1 ; i <= n ; i++)
        {
            cin >> volume[i] >> value[i] >> c[i];      // 费用，价值，数量
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
        {
            Multiplepark(value[i], volume[i], c[i]);
        }
        cout << dp[v] << endl;
    }
    return 0;
}

Three：

#include <iostream>

using namespace std;

const int MAXN = 110;
const int MAXW = 5e4 + 10;

int N, W;
int Wi[MAXN], Pi[MAXN], Ci[MAXN];
int deq[MAXW];
long long deqv[MAXW];
long long dp[MAXW];

int main()
{
    scanf("%d %d", &N, &W);

    for (int i = 0; i < N; ++i)
    {
        scanf("%d %d %d", &Wi[i], &Pi[i], &Ci[i]);
    }
    for (int i = 0; i < N; ++i)
    {
        for (int k = 0; k < Wi[i]; ++k)
        {
            int s = 0, t = 0;
            for (int j = 0; j * Wi[i] + k <= W; ++j)
            {
                long long val = dp[j * Wi[i] + k] - j * Pi[i];
                while (s < t && deqv[t - 1] <= val)
                {
                    t--;
                }
                deq[t] = j;
                deqv[t++] = val;
                dp[j * Wi[i] + k] = deqv[s] + j * Pi[i];
                if (deq[s] == j - Ci[i])
                {
                    s++;
                }
            }
        }
    }
    printf("%lld\n", dp[W]);

    return 0;
}

参考

51Nod 1085 背包问题
 《背包相关》