P2851 [USACO06DEC]最少的硬币The Fewest Coins

$[USACO06DEC]最少的硬币The Fewest Coins$

$mathcal{Description}$
农夫John想到镇上买些补给。为了高效地完成任务，他想使硬币的转手次数最少。即使他交付的硬币数与找零得到的的硬币数最少。

John想要买价值为T的东西。有N(1<=n<=100)种货币参与流通，面值分别为V1,V2…Vn (1<=Vi<=120)。John有Ci个面值为Vi的硬币(0<=Ci<=10000)。

我们假设店主有无限多的硬币，并总按最优方案找零。注意 无解输出-1.

$mathcal{Solution}$

$最初想法$
一直想着贪心去凑… 无果.

$正解部分$

假设最优方案 $John$ 的支出为 $sum$ , 则找零为 $sum-T$ ,

则问题转化为:

使用 $John$ 现有的硬币凑出 $sum$ , 要求使用种类数尽量少.
使用任意数量的硬币凑出 $sum-T$ , 要求使用种类数尽量少.

则 $问题1$ 为 多重背包, $问题2$ 为 完全背包.
背包容量为 $sum,sum-T$ ,
物品重量为 $V_i$ , 物品价值为 $1$ ,

于是考虑如何枚举 $John$ 的支出,
下界显然为 $T$ , 上界为 $T+V_{max}^2$ .

$实现部分$
按照上方解法,
枚举 $sum$ , 此时需要将 多重背包 拆分成 01背包 进行 $dp$ ,

若暴力拆分, 则复杂度为 $O(N*10000*T)$ , $color{red}{爆炸!}$ .
但若 二进制 拆分, 则复杂度为 $O(N*log10000 * T)$ , 其中 $log10000≈13.29$ ,
所以采用 二进制拆分 即可.
求出答案为 $res_1$ ,

对于另一个 完全背包, 求出答案为 $res_2$ ,
则 $Ans=min(res_1+res_2)$ .

$mathcal{Code}$

bug

#include<bits/stdc++.h>
#define reg register

const int maxn = 105;
const int inf = 0x3f3f3f3f;

int N;
int T;
int maxx;

int V[maxn];
int C[maxn];
int F1[25005];
int F2[25005];

void Work(){
        memset(F1, 0x3f, sizeof F1); F1[0] = 0;
        memset(F2, 0x3f, sizeof F2); F2[0] = 0;
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = V[i]; j <= maxx; j ++)
                        F1[j] = std::min(F1[j], F1[j-V[i]] + 1);

        for(reg int i = 1; i <= N; i ++){
                for(reg int k = 1; k <= C[i]; k <<= 1){
                        for(reg int j = T+maxx; j >= V[i]*k; j --) F2[j] = std::min(F2[j], F2[j-V[i]*k] + k);
                        C[i] -= k;
                }
                if(C[i] > 0)
                        for(reg int j = T+maxx; j >= V[i]*C[i]; j --) 
                                F2[j] = std::min(F2[j], F2[j-V[i]*C[i]] + C[i]);
        }
        int Ans = inf;
        for(reg int i = T; i <= T+maxx; i ++)
                Ans = std::min(Ans, F1[i-T] + F2[i]);
        printf("%d
", Ans>=inf?-1:Ans);
}

int main(){
        scanf("%d%d", &N, &T);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &V[i]), maxx = std::max(V[i]*V[i], maxx);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &C[i]);
        Work();
        return 0;
}