poj 1276 Cash Machine 背包问题

浏览数：36 / 时间：2015年06月20日

题目链接：http://poj.org/problem?id=1276

背包问题的动态规划

照着背包九讲打了个模板

此题特殊在重量和价值相等而模板更具有一般性

在算f的过程中及时更新最大值

复杂度：V * Σ(log n[i])

注意初始化

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <stack>
#include <set>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 20;
const int maxc = 100010;

int f[maxc];
int n[maxn], d[maxn], w[maxn];
int c, N;
int ans;

void ZeroOnePack(int cost, int weight)
{
    for(int i = c; i >= cost; i--)
    {
        f[i] = max(f[i], f[i-cost] + weight);
        if(f[i] > ans)
            ans = f[i];
    }
}

void CompletePack(int cost, int weight)
{
    for(int i = cost; i <= c; i++)
    {
        f[i] = max(f[i], f[i-cost] + weight);
        if(f[i] > ans)
            ans = f[i];
    }
}

void MultiplePack(int cost, int weight, int amount)
{
    if(cost*amount >= c)
    {
        CompletePack(cost, weight);
        return;
    }
    int k = 1;
    while(k < amount)
    {
        ZeroOnePack(k*cost, k*weight);
        amount = amount - k;
        k *= 2;
    }
    ZeroOnePack(amount*cost, amount*weight);
}

int main()
{
    //freopen("in.txt", "r", stdin);

    while(scanf("%d%d", &c, &N) == 2)
    {
        ans = 0;
        memset(f, 0, sizeof(f));

        for(int i = 0; i < N; i++)
        {
            scanf("%d%d", &n[i], &d[i]);
        }

        for(int i = 0; i < N; i++)
        {
            w[i] = d[i];
        }

        for(int i = 0; i < N; i++)
            MultiplePack(d[i], w[i], n[i]);

        printf("%d\n", ans);
    }

    return 0;
}