POJ 3260 The Fewest Coins ( Knapsack multiple & complete DP )

3260 -- The Fewest Coins
n ≤ 100 types of currency exists, each value v[i] ≤ 120, and I have c[i] ≤ 100 of them. Answer the minimum sum of coins that I have to give and take, when I am to buy a product of T ≤ 10000 dollars.
This is basically a problem of both complete knapsack and multiple knapsack combined. However, it is a little tricky to decide the maximum bound of the number of coins that we should give. Although t * 2 seems to be enough, but actually the tight bound is maxv * maxv. I saw it from this article
背包问题--POJ 3260 The Fewest Coins【完全背包+多重背包】 - AndreMouche - 博客园
proved by Pigeonhole principle - Wikipedia, the free encyclopedia.

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXT = 1e4 + 4;
const int MAXN = 100 + 2;
const int MAXV = 120 + 1;
const int MAXC = 1e4 + 4;
const int INF = 1e9;

int n, t;
int v[MAXN], c[MAXN];
int maxv;
int mtot[MAXT + MAXV * MAXV], mmul[MAXT + MAXV * MAXV];

void upmin(int &a, int b){ a = min( a, b ); }

void dp_total(int n, int lim){
    fill( mtot, mtot + lim + 1, INF );
    mtot[0] = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j + v[i] <= lim; ++j)
            upmin( mtot[ j + v[i] ], mtot[j] + 1 );
}

void dp_multi(int n, int lim){
    fill( mmul, mmul + lim + 1, INF );
    mmul[0] = 0;
    for(int i = 0; i < n; ++i){
        int num = c[i];
        for(int k = 1; num > 0; k <<= 1){ // binary enumeration
            int mul = min( k, num );
            for(int j = lim - v[i] * mul; j >= 0; --j)
                upmin( mmul[ j + v[i] * mul ], mmul[j] + mul );
            num -= mul;
        }
    }
}

void solve(){
    dp_total( n, maxv * maxv );
    dp_multi( n, t + maxv * maxv );
    int ans = INF;
    for(int i = maxv * maxv; i >= 0; --i)
        upmin( ans, mtot[i] + mmul[t + i] );
    if( ans == INF ) puts("-1");
    else printf("%d\n", ans);
}

int main(){
    scanf("%d %d", &n, &t);
    for(int i = 0; i < n; ++i){
        scanf("%d", &v[i]);
        maxv = max( maxv, v[i] );
    }
    for(int i = 0; i < n; ++i)
        scanf("%d", &c[i]);
    solve();
    return 0;
}