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

$\left[USACO06DEC\right]最少的硬币TheFewestCoins$[USACO06DEC]最少的硬币The Fewest Coins

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

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

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

$Solution$Solution

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

$正解部分$正解部分

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

则问题转化为:

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

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

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

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

若 暴力拆分, 则复杂度为 $O(N\ast 10000\ast T)$O(N∗10000∗T), $爆炸!$爆炸!.
但若 二进制 拆分, 则复杂度为 $O(N\ast log10000\ast T)$O(N∗log10000∗T), 其中 $log10000\approx 13.29$log10000≈13.29,
所以采用 二进制拆分 即可.
求出答案为 $re{s}_1$res1​,

对于另一个 完全背包, 求出答案为 $re{s}_2$res2​,
则 $Ans=min(re{s}_1+re{s}_2)$Ans=min(res1​+res2​) .

$Code$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\n", 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;
}