POJ #1276

I tried several solutions except the one from http://love-oriented.com/pack/P03.html (wonderful resource to learn DP), but all failed with WATLE.  After adopting Tianyi Cui's solution, I got AC. (Reference: http://blog.163.com/xiangzaihui@126/blog/static/1669557492011726819133/)

Optimization 1: Binary optimization on choices of counts. Without this, TLE could happen. What's interesting, the complete packing section is optional.

This is a multiple knapsack problem based on 0-1 packingcomplete packing. This is my AC code (47MS with complete packing section, 57MS without)

//    POJ 1276
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 11
#define MAX_CNT 100005
#define Max(a,b) (a) > (b) ? (a) : (b)

int dp[MAX_CNT] = { 0 };
int v;

void ZeroOnePack(int cost, int weight)
{
    for (int i = v; i >= cost; i--)
        dp[i] = Max(dp[i], dp[i - cost] + weight);
}

void CompletePack(int cost, int weight)
{
    for (int i = cost; i <= v; i++)
        dp[i] = Max(dp[i], dp[i - cost] + weight);
}

void MultiplePack(int cost, int weight, int n)
{
    if (cost * n > v)
    {
        CompletePack(cost, weight);
    }
    else
    {
        int k = 1;
        while (k < n)
        {
            ZeroOnePack(cost * k, weight * k);
            n -= k;
            k *= 2;
        }
        ZeroOnePack(cost * n, weight * n);
    }
}

int main()
{
    int n;
    while (scanf("%d %d", &v, &n) != EOF)
    {
        //    Get input        
        int cnt[MAX_N] = { 0 }, val[MAX_N] = { 0 };        
        for (int i = 0; i < n; i++)    scanf("%d %d", cnt + i, val + i);

        if (v == 0 || n == 0)
        {
            printf("0
"); continue;
        }

        //    Init
        for (int i = 0; i < MAX_CNT; i++) dp[i] = 0;
        
        //    背包九讲
        for (int i = 0; i < n; i++)
            MultiplePack(val[i], val[i], cnt[i]);

        printf("%d
", dp[v]);
    }

    return 0;
}