189A. Cut Ribbon

brute force/dp, 1300, https://codeforces.com/problemset/problem/189/A

Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:

After the cutting each ribbon piece should have length a, b or c.
After the cutting the number of ribbon pieces should be maximum.

Help Polycarpus and find the number of ribbon pieces after the required cutting.

Input

The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.

Output

Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

Examples

input

5 5 3 2

output

input

7 5 5 2

output

Note

In the first example Polycarpus can cut the ribbon in such way: the first piece has length 2, the second piece has length 3.

In the second example Polycarpus can cut the ribbon in such way: the first piece has length 5, the second piece has length 2.

思路：就是一个需要刚好装满的完全背包问题，只有三种商品a, b, c，能取无限件物品，每件物品价值是1，求最大价值。

python

n, a, b, c = map(int, input().split())
dp = [0]+[float('-inf')]*n

for i in range(1, n+1):
    for j in (a, b, c):
        if i >= j:
            dp[i] = max(dp[i-j] + 1, dp[i])

print(dp[n])

2020fall-cs101，王君宇。这道题状态转移方程就是 d[i]=max(d[i-a],d[i-b],d[i-c])+1，其中初始量是 0.到达一个新节点的方法有三种：+a、+b、+c，选取最大增量即可，思路十分精巧。

2020fall-cs101，黄旭。找到递推公式 dp[i] = max(dp[i-a], dp[i-b], dp[i-c]) + 1就好了。

python

n,a,b,c = map(int,input().split())
dp = [0]+[-4000]*4000
for i in range(1,n+1):
    dp[i] = max(dp[i-a], dp[i-b], dp[i-c]) + 1
print(dp[n])

https://python-forum.io/thread-23120.html

At the beginning of the procedure, the indexes i-a, i-b, i-c can be negative, which means that python is going to take values at the end of the array, because for example d[-4] is the 4th value from the right. Initializing the array to a large negative value in each cell is intended as giving the cell a "negative infinite" value for the max algorithm. At every step, an increment of 1 is added, so the number is chosen large enough so that -1e9 + 4000 < 0

python

n, a, b, c = map(int, input().split())
d = [0] + [-1e9] * 4000
for i in range(1, n + 1):
    d[i] = max(d[i - a], d[i - b], d[i - c]) + 1
print(d[n])

2020fall-cs101，赵春源。这是一个简单的DP思想，我们让f~i~等于把i按题意切开所得的最大段数，我们让 $f_{0} = 0$ ，其他的位置为负无穷，表示这个长度没法按题目的要求切开，我们考虑如何用较小的f推出较大的f，当然是把a,b,c三种切法都试一遍，最大长度就是 $m a x (f [i - a], f [i - b], f [i - c]) + 1$

python

n, a, b, c = map(int, input().split())
f = (n+1) * [-10000]
f[0] = 0
for i in range(1, n+1):
    if i >= a:
        f[i] = max(f[i], f[i - a] + 1)
    if i >= b:
        f[i] = max(f[i], f[i - b] + 1)
    if i >= c:
        f[i] = max(f[i], f[i - c] + 1)
print(f[n])

2022fall-cs101，朱骏豪，工程院

一开始想试着写枚举，竟然就过了

python

n,a,b,c=[int(x) for x in input().split()]
num=[]
if a==1 or b==1 or c==1:
    print(n)
else:
    for i in range(int(n/a)+1):
        t=n-i*a
        for j in range(int(t/b)+1):
            w=t-j*b
            if w%c==0:
                num.append(i+j+int(w/c))
    print(max(num))

暴力，AC时间186ms

python

# 冯全璟 24物理学院
n, a, b, c = map(int, input().split())
dui = sorted([a, b, c])
ans = 0

# 遍历 i 的所有可能值
for i in range(n // dui[2] + 1):
    da = n - i * dui[2]
    if da < 0:
        break  # 提前终止外层循环

    # 遍历 j 的所有可能值
    for j in range(da // dui[1] + 1):
        remaining = da - j * dui[1]
        if remaining < 0:
            break  # 提前终止内层循环

        if remaining % dui[0] == 0:
            k = remaining // dui[0]
            ans = max(ans, i + j + k)
            break  # 剪枝，找到一个解后跳出内层循环

print(ans)

2020fall-cs101，成泽恺。一开始直接想暴力循环，三个片段a，b，c，一开始假设他可以分成i个a和j个b，i，j初始值都为0，while a~i~和a~i~+b~j~比n小的时候循环判断能不能加c片段进去，如果可以用max函数拿到此刻的片段数目的最大值，直到最后输出num即可，但这样用python3会超时，pypy3可以过。

python

n,a,b,c = map(int, input().split())
num = 0
i = 0
j = 0
while a*i <= n:
    j = 0
    while b*j+a*i <= n:
        d = n - a*i - b*j
        if d%c==0 and a*i+b*j<=n:
            num = max(num, i+j+d//c)
        j += 1

    i += 1
 
print(num)

暴力解法，在test 37超时。

Test: #37 Input 4000 1 1 1

python

def f(n, a, b, c):
    num = 0

    # 优化外层循环的范围
    max_i = n // a
    for i in range(max_i + 1):
        remaining_n_after_a = n - a * i

        # 优化内层循环的范围
        max_j = remaining_n_after_a // b
        for j in range(max_j + 1):
            d = remaining_n_after_a - b * j

            # 检查 d 是否可以被 c 整除
            if d >= 0 and d % c == 0:
                k = d // c
                num = max(num, i + j + k)

    return num


n, a, b, c = map(int, input().split())
print(f(n, a, b, c))

题目需要用到动态规划，这个问题相当于一个完全背包，背包容量是n，有重量为a，b，c的物品，物品价值都是1，求取在恰好装满背包的情况下价值最大。因为题目保证有解，开一个长度为n+1的列表，初始值为-9999（避免背包不被恰好装满的情况出现），容量为0的时候价值为0，容量为i的时候判断能不能放下重量为a，b，c的片段，如果能查看背包剩余容量i-a可以放多少，如果i-a不能被恰好填满，由于初始值是很大的负值，在装进去之后仍然是负值，不会影响最终结果。循环n次，最后得到最优解。

2020fall-cs101，刘安澜。思路：看上去这个题和老师上课讲的dp是一个镜像关系的题目，所以就按照找硬币的dp思路写了最初始的一版。但是不同于找硬币必有一个解，剪丝带对于某些丝带长度是无法分割的，所以这也就造成了在某些不能分割的长度上输出错误的结果。所以对于这种情况需要我们将除0外所有的初始值都赋为一个很大的负数，这样就能很好避免不能分割的长度对于其它可分割长度答案的扰动。

python

def dpcut( lengthlist, l, maxcuts ):
    for i in range( l + 1 ):
        for j in [ c for c in lengthlist if c <= i ]:
            if maxcuts[i-j] + 1 > maxcuts[i]:
                maxcuts[i] = maxcuts[i-j] + 1
    return maxcuts[l]

l,a,b,c = map(int,input().split())
lengthlist = [a, b, c]
maxcuts = [0] + [-1000000]*l

print( dpcut( lengthlist, l, maxcuts ) )

2022fall-cs101，杨文可

思路与课件上的找零问题完全一样。不同的是，有一些长度的彩带是剪不了的。要想办法避免这些长度参与递推之后影响最终的结果。单纯把它们赋值成-1不行，因为递推几次以后就变成正的了。所以要赋值成足够大的负数。

max() 的参数要么是一整个可迭代类型, 要么是逗号分隔的多个数值，不能是两者混合。

python

n, a, b, c = map(int, input().split()) 
dp = [0] + [-4000] * n  
for i in range(n + 1):  
    dp[i] = max([dp[i - x] + 1 for x in [a, b, c] if x <= i] + 
[dp[i]])  
print(dp[-1])

2021fall-cs101，唐浴歌

经验总结的一点是，dp的题好像一般都只需两次遍历就能解决了：

1）第一次遍历（初始化）：首先要保证dp列表项数足够充裕。如求的是可及性的话，dp列表里的能被目标数整除的项都+1。2.第二次遍历（特殊化处理）：根据题目要求对完成初始化的dp作处理。由于有最优目标，每一次处理都会判断大小关系来迭代掉之前的结果。

闫老师批注：两遍处理的思路挺好。第一遍是数据预处理，这样第二遍就很清楚了。充实的寒假生活（http://cs101.openjudge.cn/practice/16528/），也可以如法炮制。

python

# 2021fall-cs101, TAN Yuge
n, *m = map(int, input().split())
dp = [0] * (n + 1) 
for i in m:     
    for j in range(1, n + 1):         
        if j % i == 0:             
            dp[j] = max(j // i, dp[j])
            
for i in range(1, n +  1):    
    for j in m:         
        if i > j and dp[i - j]:             
            dp[i] = max(dp[i - j] + 1, dp[i])
print(dp[n])

扩欧（3个物品才比较优），枚举一个变量对另外两个解不定方程。

python

# 高景行 24数学科学学院
def swap(a, b):
    return b, a

def exgcd(a, b):
    if not b:
        return a, 1, 0
    d, x, y = exgcd(b, a % b)
    return d, y, x - (a // b) * y

# 读取输入值
n, a, b, c = map(int, input().split())  # ax + by = n
if a < b:
    a, b = swap(a, b)

# 扩展欧几里得算法，求解最大公约数和初始解
d, x0, y0 = exgcd(a, b)
ans = 0

# 化简 a 和 b
a //= d
b //= d

# 枚举 i，计算可能的解
for i in range(n // c + 1):
    remainder = n - c * i
    if remainder % d != 0:
        continue

    C = remainder // d
    tmpx = (x0 * C % b + b) % b

    if C < a * tmpx:
        continue

    # 计算 ans，尝试取最大值
    ans = max(ans, tmpx + (C - a * tmpx) // b + i)

# 输出结果
print(ans)

思路：和小偷背包的思路很像，建立二维数组表示要切掉a，b，c中一段的最大段数，然后取最大值。

python

# 陈一匡 24物理学院
n,a,b,c=map(int,input().split())
d=[a,b,c]
l=[[0]+[-1]*n for _ in range(3)]
for i in range(1,n+1):
    for j in range(3):
        if i>=d[j]:
            l[j][i]=max(l[0][i-d[j]],l[1][i-d[j]],l[2][i-d[j]])+1
            if l[j][i]==0:
                l[j][i]=-1
print(max(l[0][n],l[1][n],l[2][n]))

189A. Cut Ribbon ​

189A. Cut Ribbon