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

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;
}
```