a981: 求和問題
n m (1<=n<=30, 1<=m<=100000000)
n個正整數, 全部以空格分開
10 100
10 20 40 30 50 80 60 70 5 155 10 15 20 50
5 10 15 30 40
5 10 15 70
5 15 20 60
5 15 30 50
5 15 80
10 20 30 40
10 20 70
10 30 60
10 40 50
20 30 50
20 80
30 70
40 60'''
由於要由小至大輸出，所以先把數字按順序排好，接下來窮舉全部的可能，
如果窮舉過程中被窮舉到的值相加等於目標值則印出答案。
因為窮舉到的值相加超過目標值之後不可能再出現”窮舉到的值總和 = 目標值”的情況，
所以可以把它剪枝掉。
又因為窮舉的陣列已經被排序過了，下一個窮舉值必 ≥ 當前窮舉值，
所以當窮舉到的值總和 + 當前的窮舉值 > 目標值時，接下來也都不可能再
出現”窮舉到的值總和 = 目標值”，所以當發生這種情況時也可以進行剪枝。
Sum,start,depth=0,0,0
n,m,Next=0,0,0
a_list,b_list=[],[]
output=[]
noAns=''
def dfs(Sum, start, depth):
for i in range (start , n):
Next = Sum + a_list[i]
if (Next >= m):
if (Next == m):
for j in range(0 , depth):
print('%d ' %( output[j]),end='-')
print('%d' %(a_list[i]))
noAns = 0;
if (a_list[i] < a_list[i + 1]):
print(a_list[i] , a_list[i + 1])
return
#print('depth -->', depth,a_list[i])
output[depth] = a_list[i]
if (Next + a_list[i] <= m):
#print('Next-->', Next, i + 1, depth + 1)
dfs(Next, i + 1, depth + 1)
'''
def recursive(n , N , m , total) :
# int N,int n,int t,int total
if(total>m):
return
if(N==n):
Sum=0
for i in range (0,n):
if(s[i]==1):
Sum=Sum + a_list[i];
if(Sum==m):
for i in range(0 , n ):
if(s[i]==1):
print('%d' %(a_list[i]),end='-')
flag=1
print('\n')
return
s[N]=1;
total=total + a_list[N]
recursive(n,N+1,m,total)
total=total - a_list[N]
s[N]=0;
recursive(n,N+1,m,total);
#--------------------------------------------
total,N=0,0
s=[]
flag=0
print('a981: 求和問題')
while True:
try:
n,m=map(int, input('請輸入n 和 m 兩個數字 -->').split())
b_list= list(map(int, input('請輸入n 個 數字-->').split()))
a_list= sorted(b_list)
print(n,m,a_list,'\n')
for i in range (0,n+1):
s.append(' ')
recursive(n,0,m,0)
if (flag==0):
print('-1\n')
except:
break
>>> %Run a981.py
a981: 求和問題
請輸入n 和 m 兩個數字 -->10 100
請輸入n 個 數字-->10 20 40 30 50 80 60 70 5 15
10 100 [5, 10, 15, 20, 30, 40, 50, 60, 70, 80]
5-10-15-20-50-
5-10-15-30-40-
5-10-15-70-
5-15-20-60-
5-15-30-50-
5-15-80-
10-20-30-40-
10-20-70-
10-30-60-
10-40-50-
20-30-50-
20-80-
30-70-
40-60-
-1
請輸入n 和 m 兩個數字 -->
>>>
沒有留言:
張貼留言