两种物品 A,BA,BA,B,一种物品能买多次,买一个价值分别为 v1,v2v1,v2v1,v2,代价为 w1,w2w1,w2w1,w2,求最少用多少代价达到 KKK 价值。
了解到做法是枚举 AAA 的个数 t1∈[0,v2)t1\in[0,v2)t1∈[0,v2) 或者 BBB 的个数 t2∈[0,v1)t2\in[0,v1)t2∈[0,v1),然后直接算,O(v1+v2)O(v1+v2)O(v1+v2)。
求问有没有复杂度更优的/kel