T01742: Coins

dp, http://cs101.openjudge.cn/routine/01742/

People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch. You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.

输入

The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.

输出

For each test case output the answer on a single line.

样例输入

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

样例输出

8
4

来源

LouTiancheng@POJ

python

# 23n2300010763，数院胡睿诚
'''
多重背包问题 (二进制优化)
多重背包问题通常可转化成01背包问题求解。但若将每种物品的数量拆分成多个1的话，时间复杂度会很高，
从而导致TLE。所以，需要利用二进制优化思想。即:一个正整数n，可以被分解成1,2,4,...,2^(k-1),
n-2^k+1的形式。其中，k是满足n-2^k+1>0的最大整数。
例如，假设给定价值为2，数量为10的物品，依据二进制优化思想可将10分解为1+2+4+3，则原来价值为2,
数量为10的物品可等效转化为价值分别为1*2，2*2，4*2，3*2，即价值分别为2，4，8，6，数量均为1的物品。

def sum_2(x):
    s = 0
    while x > 0:
        s += (x & 1)
        x = x >> 1
    return s

'''
import math

while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    ls = list(map(int, input().split()))
    w = (1 << (m + 1)) - 1  # e.g., m=10, w=2047
    result = 1
    for i in range(n):
        number = ls[i + n] + 1  # e.g., number = 10
        limit = int(math.log(number, 2))  # limit = 3
        rest = number - (1 << limit)  # rest = 3
        # 处理 2 的幂次方部分
        for j in range(limit):
            shift = ls[i] * (1 << j)
            result = (result | (result << shift)) & w

        # 处理剩余部分
        if rest > 0:
            result = (result | (result << (ls[i] * rest))) & w
    # print(sum_2(result) - 1)
    print(bin(result).count('1') - 1)

result = 1 是必要的前提：表示初始只有和为 0 的状态。
number + 1 的目的是确保所有二进制分解的情况被正确处理，但前提是 result 的初始值为 1。

用了bin函数，比自己写的sum_2快了很多。

python内置函数执行特别快，如sort, find，即使用同样方法实现，也没有直接调用函数快。是因为内置函数都是C语言实现编译成可执行文件库了？

是的，Python内置函数在执行速度上通常会比用纯Python代码实现的相同功能更快。这是因为很多内置函数（如sort、find等）实际上是用C语言实现的，并且在Python解释器中以编译成的可执行文件库的形式存在。相比于纯Python代码，C语言的执行速度更快，这是由于C语言的底层实现更加高效。因此，当使用内置函数时，Python解释器可以直接调用这些C语言实现的函数，从而获得更快的执行速度。

另外，Python解释器本身也会对一些常用的操作进行优化，比如将循环展开、使用位运算等技巧，以提高执行效率。这些优化也可以帮助内置函数获得更好的性能。

需要注意的是，并不是所有的内置函数都是用C语言实现的，有一些内置函数的实现可能是用Python编写的。但是，Python标准库中的绝大部分内置函数都是用C实现的，因此它们通常具有很高的执行速度。

AI解析：
这段代码解决的是一个变种的背包问题，具体是多重背包问题（Multiple Knapsack Problem）。问题的目标是计算给定若干种不同面额的硬币及其数量，Tony可以支付的所有金额的数量，要求每种金额至少支付一次，且金额的最大值不超过 m。
下面是对代码的详细解读。
1. 输入与问题描述
首先，代码从输入中读取了多个测试用例，每个测试用例包含：
n：硬币的种类数。
m：Tony要支付的最大金额。
接下来的一行输入包含了 2n 个整数，其中：
A1, A2, ..., An 是每种硬币的面额。
C1, C2, ..., Cn 是对应硬币的数量。
目标是计算，Tony可以支付的金额 1 到 m 之间，有多少种金额可以用手头的硬币组合起来支付。
2. 核心思想：多重背包问题
每种硬币的数量是有限的，因此这是一个多重背包问题。常见的背包问题是物品数量无限多，但在这个问题中每种硬币的数量是有限的。解决方法之一是利用二进制优化，这是一种将多重物品转换成多个单一物品的方法，从而避免暴力穷举。
3. 二进制优化
假设我们有一种面额的硬币，它的数量是 Ci。我们可以将这 Ci 个硬币按照二进制的形式拆分。例如，如果有 Ci = 10 个面额为 Ai 的硬币，可以拆成如下形式：
1 个硬币
2 个硬币
4 个硬币
3 个硬币
这种拆分方法的作用是通过减少物品的数量，避免了暴力方法中重复的操作，从而提升了算法效率。
4. 代码分析
下面逐步分析代码中的关键部分：
主循环处理多个测试用例
python
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    ls = list(map(int, input().split()))
这部分代码读取每个测试用例的输入，并判断是否结束。如果 n 和 m 都是 0，就停止循环。
准备数据
python
w = (1 << (m + 1)) - 1  # e.g., m=10, w=2047
result = 1
这里 w 是一个掩码，用来表示所有可能的金额。1 << (m + 1) 计算的是 2^(m+1)，减去 1 得到的 w 是一个具有 m+1 位的全1二进制数，用来存储可以支付的金额。
result 是一个用于存储当前能支付的金额的状态变量，初始化为 1，即表示只有金额为 0 可以支付。
二进制优化
python
for i in range(n):
    number = ls[i + n] + 1   # e.g., number = 10
    limit = int(math.log(number, 2))  # limit = 3
    rest = number - (1 << limit)  # rest = 3
这里，对于每种硬币，首先计算出它的数量 number（ls[i + n] 是硬币的数量），然后计算 limit，即 number 可以被分解为多少个二进制的部分。rest 是剩下的硬币数量。
对硬币进行二进制拆分并更新状态
python
for j in range(limit):
    result = (result | (result << (ls[i] * (1 << j)))) & w
if rest > 0:
    result = (result | (result << (ls[i] * rest))) & w
对于每种硬币，按照二进制拆分的方式，更新 result 变量。通过 result | (result << ...) 操作，可以模拟在已有的金额基础上，添加新的硬币组合的所有可能支付金额。
输出结果
python
print(bin(result).count('1') - 1)
bin(result) 将 result 转换为二进制字符串，count('1') 统计其中 1 的个数，表示能支付的金额的种类数。减去 1 是因为 result 包含了金额 0，而题目要求的是从 1 到 m 的金额。
5. 完整代码示例
python
import math

while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    ls = list(map(int, input().split()))
    
    w = (1 << (m + 1)) - 1  # e.g., m=10, w=2047
    result = 1  # Initially, we can only pay amount 0
    
    for i in range(n):
        number = ls[i + n] + 1  # Number of coins of value ls[i]
        limit = int(math.log(number, 2))  # The maximum number of binary splits
        rest = number - (1 << limit)  # Remaining coins after the maximum split
        
        for j in range(limit):
            result = (result | (result << (ls[i] * (1 << j)))) & w
        
        if rest > 0:
            result = (result | (result << (ls[i] * rest))) & w
    
    # The result now contains the number of ways we can pay amounts from 1 to m
    print(bin(result).count('1') - 1)  # Subtract 1 to exclude amount 0
6.复杂度
时间复杂度：由于每种硬币最多进行 O(log Ci) 次操作，总的时间复杂度是 O(n * log Ci)，其中 Ci 是硬币的数量。每次操作中涉及到二进制位的操作和状态更新。
空间复杂度：主要是 result 的存储，空间复杂度是 O(m)。
7.总结
这段代码解决的是多重背包问题，并通过二进制优化技巧避免了暴力方法中的重复计算，提升了效率。

T01742: Coins ​

T01742: Coins