AlgorithmsByPython/Dynamic Programming.py at master · lanhaixuan/AlgorithmsByPython · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 解决动态规划中的找零问题
# 输入需要找零的金额和货币的币值向量
# 输出满足找零条件的最少的硬币个数
defChangeMaking(coinVal, change):
alist= [0]*(change+1)
foriinrange(1, change+1):
temp=change; j=0
whilej<=len(coinVal)-1andi>=coinVal[j]:
temp=min(alist[i-coinVal[j]], temp)
j+=1
alist[i] =temp+1
returnalist.pop()

print(ChangeMaking([1, 5, 10, 25], 63))

# 解决动态规划中的币值最大化问题---在满足所选硬币不相邻的条件下,从一堆硬币中选择最大金额的硬币
# 输入数组C[1..n]保存n个硬币的面值
# 输出可选硬币的最大金额
defcoinRow(coinrow):
alist= [0]*(len(coinrow)+1)
alist[1] =coinrow[0]
foriinrange(2, len(coinrow)+1):
alist[i] =max(coinrow[i-1]+alist[i-2], alist[i-1])
returnalist.pop()

print(coinRow([5, 1, 2, 10, 6, 2]))

# 解决0-1背包问题
defmaxBag(weight, value, totalWeight):
iflen(weight) <=0orlen(value) <=0ortotalWeight<=0orlen(weight) !=len(value):
return
num=len(weight)
tempMat= []
foriinrange(num+1):
tempMat.append([0]*(totalWeight+1))
foriinrange(1, num+1):
forjinrange(1, totalWeight+1):
ifj-weight[i-1] >=0:
tempMat[i][j] =max(tempMat[i-1][j], value[i-1] +tempMat[i-1][j-weight[i-1]])
else:
tempMat[i][j] =tempMat[i-1][j]
returntempMat[-1][-1]

weight, value, totalWeight= [2,1,3,2], [12,10,20,15], 5
print(maxBag(weight, value, totalWeight))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 解决动态规划中的找零问题
# 输入需要找零的金额和货币的币值向量
# 输出满足找零条件的最少的硬币个数
defChangeMaking(coinVal, change):
alist= [0]*(change+1)
foriinrange(1, change+1):
temp=change; j=0
whilej<=len(coinVal)-1andi>=coinVal[j]:
temp=min(alist[i-coinVal[j]], temp)
j+=1
alist[i] =temp+1
returnalist.pop()

print(ChangeMaking([1, 5, 10, 25], 63))

# 解决动态规划中的币值最大化问题---在满足所选硬币不相邻的条件下,从一堆硬币中选择最大金额的硬币
# 输入数组C[1..n]保存n个硬币的面值
# 输出可选硬币的最大金额
defcoinRow(coinrow):
alist= [0]*(len(coinrow)+1)
alist[1] =coinrow[0]
foriinrange(2, len(coinrow)+1):
alist[i] =max(coinrow[i-1]+alist[i-2], alist[i-1])
returnalist.pop()

print(coinRow([5, 1, 2, 10, 6, 2]))

# 解决0-1背包问题
defmaxBag(weight, value, totalWeight):
iflen(weight) <=0orlen(value) <=0ortotalWeight<=0orlen(weight) !=len(value):
return
num=len(weight)
tempMat= []
foriinrange(num+1):
tempMat.append([0]*(totalWeight+1))
foriinrange(1, num+1):
forjinrange(1, totalWeight+1):
ifj-weight[i-1] >=0:
tempMat[i][j] =max(tempMat[i-1][j], value[i-1] +tempMat[i-1][j-weight[i-1]])
else:
tempMat[i][j] =tempMat[i-1][j]
returntempMat[-1][-1]

weight, value, totalWeight= [2,1,3,2], [12,10,20,15], 5
print(maxBag(weight, value, totalWeight))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 解决动态规划中的找零问题
# 输入需要找零的金额和货币的币值向量
# 输出满足找零条件的最少的硬币个数
defChangeMaking(coinVal, change):
alist= [0]*(change+1)
foriinrange(1, change+1):
temp=change; j=0
whilej<=len(coinVal)-1andi>=coinVal[j]:
temp=min(alist[i-coinVal[j]], temp)
j+=1
alist[i] =temp+1
returnalist.pop()

print(ChangeMaking([1, 5, 10, 25], 63))

# 解决动态规划中的币值最大化问题---在满足所选硬币不相邻的条件下,从一堆硬币中选择最大金额的硬币
# 输入数组C[1..n]保存n个硬币的面值
# 输出可选硬币的最大金额
defcoinRow(coinrow):
alist= [0]*(len(coinrow)+1)
alist[1] =coinrow[0]
foriinrange(2, len(coinrow)+1):
alist[i] =max(coinrow[i-1]+alist[i-2], alist[i-1])
returnalist.pop()

print(coinRow([5, 1, 2, 10, 6, 2]))

# 解决0-1背包问题
defmaxBag(weight, value, totalWeight):
iflen(weight) <=0orlen(value) <=0ortotalWeight<=0orlen(weight) !=len(value):
return
num=len(weight)
tempMat= []
foriinrange(num+1):
tempMat.append([0]*(totalWeight+1))
foriinrange(1, num+1):
forjinrange(1, totalWeight+1):
ifj-weight[i-1] >=0:
tempMat[i][j] =max(tempMat[i-1][j], value[i-1] +tempMat[i-1][j-weight[i-1]])
else:
tempMat[i][j] =tempMat[i-1][j]
returntempMat[-1][-1]

weight, value, totalWeight= [2,1,3,2], [12,10,20,15], 5
print(maxBag(weight, value, totalWeight))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 解决动态规划中的找零问题
# 输入需要找零的金额和货币的币值向量
# 输出满足找零条件的最少的硬币个数
defChangeMaking(coinVal, change):
alist= [0]*(change+1)
foriinrange(1, change+1):
temp=change; j=0
whilej<=len(coinVal)-1andi>=coinVal[j]:
temp=min(alist[i-coinVal[j]], temp)
j+=1
alist[i] =temp+1
returnalist.pop()

print(ChangeMaking([1, 5, 10, 25], 63))

# 解决动态规划中的币值最大化问题---在满足所选硬币不相邻的条件下,从一堆硬币中选择最大金额的硬币
# 输入数组C[1..n]保存n个硬币的面值
# 输出可选硬币的最大金额
defcoinRow(coinrow):
alist= [0]*(len(coinrow)+1)
alist[1] =coinrow[0]
foriinrange(2, len(coinrow)+1):
alist[i] =max(coinrow[i-1]+alist[i-2], alist[i-1])
returnalist.pop()

print(coinRow([5, 1, 2, 10, 6, 2]))

# 解决0-1背包问题
defmaxBag(weight, value, totalWeight):
iflen(weight) <=0orlen(value) <=0ortotalWeight<=0orlen(weight) !=len(value):
return
num=len(weight)
tempMat= []
foriinrange(num+1):
tempMat.append([0]*(totalWeight+1))
foriinrange(1, num+1):
forjinrange(1, totalWeight+1):
ifj-weight[i-1] >=0:
tempMat[i][j] =max(tempMat[i-1][j], value[i-1] +tempMat[i-1][j-weight[i-1]])
else:
tempMat[i][j] =tempMat[i-1][j]
returntempMat[-1][-1]

weight, value, totalWeight= [2,1,3,2], [12,10,20,15], 5
print(maxBag(weight, value, totalWeight))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 解决动态规划中的找零问题
# 输入需要找零的金额和货币的币值向量
# 输出满足找零条件的最少的硬币个数
defChangeMaking(coinVal, change):
alist= [0]*(change+1)
foriinrange(1, change+1):
temp=change; j=0
whilej<=len(coinVal)-1andi>=coinVal[j]:
temp=min(alist[i-coinVal[j]], temp)
j+=1
alist[i] =temp+1
returnalist.pop()

print(ChangeMaking([1, 5, 10, 25], 63))

# 解决动态规划中的币值最大化问题---在满足所选硬币不相邻的条件下,从一堆硬币中选择最大金额的硬币
# 输入数组C[1..n]保存n个硬币的面值
# 输出可选硬币的最大金额
defcoinRow(coinrow):
alist= [0]*(len(coinrow)+1)
alist[1] =coinrow[0]
foriinrange(2, len(coinrow)+1):
alist[i] =max(coinrow[i-1]+alist[i-2], alist[i-1])
returnalist.pop()

print(coinRow([5, 1, 2, 10, 6, 2]))

# 解决0-1背包问题
defmaxBag(weight, value, totalWeight):
iflen(weight) <=0orlen(value) <=0ortotalWeight<=0orlen(weight) !=len(value):
return
num=len(weight)
tempMat= []
foriinrange(num+1):
tempMat.append([0]*(totalWeight+1))
foriinrange(1, num+1):
forjinrange(1, totalWeight+1):
ifj-weight[i-1] >=0:
tempMat[i][j] =max(tempMat[i-1][j], value[i-1] +tempMat[i-1][j-weight[i-1]])
else:
tempMat[i][j] =tempMat[i-1][j]
returntempMat[-1][-1]

weight, value, totalWeight= [2,1,3,2], [12,10,20,15], 5
print(maxBag(weight, value, totalWeight))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 解决动态规划中的找零问题
# 输入需要找零的金额和货币的币值向量
# 输出满足找零条件的最少的硬币个数
defChangeMaking(coinVal, change):
alist= [0]*(change+1)
foriinrange(1, change+1):
temp=change; j=0
whilej<=len(coinVal)-1andi>=coinVal[j]:
temp=min(alist[i-coinVal[j]], temp)
j+=1
alist[i] =temp+1
returnalist.pop()

print(ChangeMaking([1, 5, 10, 25], 63))

# 解决动态规划中的币值最大化问题---在满足所选硬币不相邻的条件下,从一堆硬币中选择最大金额的硬币
# 输入数组C[1..n]保存n个硬币的面值
# 输出可选硬币的最大金额
defcoinRow(coinrow):
alist= [0]*(len(coinrow)+1)
alist[1] =coinrow[0]
foriinrange(2, len(coinrow)+1):
alist[i] =max(coinrow[i-1]+alist[i-2], alist[i-1])
returnalist.pop()

print(coinRow([5, 1, 2, 10, 6, 2]))

# 解决0-1背包问题
defmaxBag(weight, value, totalWeight):
iflen(weight) <=0orlen(value) <=0ortotalWeight<=0orlen(weight) !=len(value):
return
num=len(weight)
tempMat= []
foriinrange(num+1):
tempMat.append([0]*(totalWeight+1))
foriinrange(1, num+1):
forjinrange(1, totalWeight+1):
ifj-weight[i-1] >=0:
tempMat[i][j] =max(tempMat[i-1][j], value[i-1] +tempMat[i-1][j-weight[i-1]])
else:
tempMat[i][j] =tempMat[i-1][j]
returntempMat[-1][-1]

weight, value, totalWeight= [2,1,3,2], [12,10,20,15], 5
print(maxBag(weight, value, totalWeight))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 解决动态规划中的找零问题
# 输入需要找零的金额和货币的币值向量
# 输出满足找零条件的最少的硬币个数
defChangeMaking(coinVal, change):
alist= [0]*(change+1)
foriinrange(1, change+1):
temp=change; j=0
whilej<=len(coinVal)-1andi>=coinVal[j]:
temp=min(alist[i-coinVal[j]], temp)
j+=1
alist[i] =temp+1
returnalist.pop()

print(ChangeMaking([1, 5, 10, 25], 63))

# 解决动态规划中的币值最大化问题---在满足所选硬币不相邻的条件下,从一堆硬币中选择最大金额的硬币
# 输入数组C[1..n]保存n个硬币的面值
# 输出可选硬币的最大金额
defcoinRow(coinrow):
alist= [0]*(len(coinrow)+1)
alist[1] =coinrow[0]
foriinrange(2, len(coinrow)+1):
alist[i] =max(coinrow[i-1]+alist[i-2], alist[i-1])
returnalist.pop()

print(coinRow([5, 1, 2, 10, 6, 2]))

# 解决0-1背包问题
defmaxBag(weight, value, totalWeight):
iflen(weight) <=0orlen(value) <=0ortotalWeight<=0orlen(weight) !=len(value):
return
num=len(weight)
tempMat= []
foriinrange(num+1):
tempMat.append([0]*(totalWeight+1))
foriinrange(1, num+1):
forjinrange(1, totalWeight+1):
ifj-weight[i-1] >=0:
tempMat[i][j] =max(tempMat[i-1][j], value[i-1] +tempMat[i-1][j-weight[i-1]])
else:
tempMat[i][j] =tempMat[i-1][j]
returntempMat[-1][-1]

weight, value, totalWeight= [2,1,3,2], [12,10,20,15], 5
print(maxBag(weight, value, totalWeight))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 解决动态规划中的找零问题
# 输入需要找零的金额和货币的币值向量
# 输出满足找零条件的最少的硬币个数
defChangeMaking(coinVal, change):
alist= [0]*(change+1)
foriinrange(1, change+1):
temp=change; j=0
whilej<=len(coinVal)-1andi>=coinVal[j]:
temp=min(alist[i-coinVal[j]], temp)
j+=1
alist[i] =temp+1
returnalist.pop()

print(ChangeMaking([1, 5, 10, 25], 63))

# 解决动态规划中的币值最大化问题---在满足所选硬币不相邻的条件下,从一堆硬币中选择最大金额的硬币
# 输入数组C[1..n]保存n个硬币的面值
# 输出可选硬币的最大金额
defcoinRow(coinrow):
alist= [0]*(len(coinrow)+1)
alist[1] =coinrow[0]
foriinrange(2, len(coinrow)+1):
alist[i] =max(coinrow[i-1]+alist[i-2], alist[i-1])
returnalist.pop()

print(coinRow([5, 1, 2, 10, 6, 2]))

# 解决0-1背包问题
defmaxBag(weight, value, totalWeight):
iflen(weight) <=0orlen(value) <=0ortotalWeight<=0orlen(weight) !=len(value):
return
num=len(weight)
tempMat= []
foriinrange(num+1):
tempMat.append([0]*(totalWeight+1))
foriinrange(1, num+1):
forjinrange(1, totalWeight+1):
ifj-weight[i-1] >=0:
tempMat[i][j] =max(tempMat[i-1][j], value[i-1] +tempMat[i-1][j-weight[i-1]])
else:
tempMat[i][j] =tempMat[i-1][j]
returntempMat[-1][-1]

weight, value, totalWeight= [2,1,3,2], [12,10,20,15], 5
print(maxBag(weight, value, totalWeight))