1003, 1010, 12865

1010. 다리 놓기

    순서 없는 뽑기!
    nCk = M! / ( N! X (M -N)!)
    
	=> factorial(M)//factorial(N)//factorial(M-N)

---

1003. 피보나치 함수

      전역변수로 풀기가 가능하나 시간초과!

      n = 입력 값
      Z(n) = 총 0의 개수
      O(n) = 총 1의 개수

      Z(n) = Z(n-1) + Z(n+2)
      O(n) = O(n-1) + O(n+2) 가 성립.

      따라서 Z(0), Z(1), Z(2) 를 구하면 나머지 값도 알 수 있다.
      따라서 O(0), O(1), O(2) 를 구하면 나머지 값도 알 수 있다.

---

12865. 평범한 배낭

	냅색 알고리즘을 이용
    1.담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 
    	Fractional Knapsack Problem
    2.담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 
    	0-1Knapsack Problem
        
   여기서는 0-1 배낭문제(0-1Knapsack Problem)를 이용
   
   1) x축엔 가방 1~K 까지의 무게, y축은 물건 N개 개수 만큼의 배열을 만들어준다.
   2) 행을 차례대로 돌며 다음과 같은 알고리즘을 수행해준다.
   3-0) 현재 물건이 현재 돌고있는 무게보다 작다면 
   				[이전 물건][같은 무게] knapsack[i-1][j]를 입력해준다.
   3-1) 현재 물건을 넣어준다. 물건을 넣은 뒤의 남은 무게를 채울 수 있는 최댓값
   				knapsack[i-1][j-weight]을 위의 행에서 가져와 더해준다.
   3-2) 현재 물건을 넣어주는 것보다. 
   				다른 물건들로 채우는 값 knapsack[i-1][j]을 가져온다.
   4) 3-1과 3-2 중 더 큰 값을 knapsack[i][j]에 저장(가장 가치 높은 구성)
   ===> knapsack[N][K] = K무게일 때의 최대 가치값
   
   
   

# N, K  = 4 , 7
# W = [0, 6, 4, 3, 5]
# V = [0, 13, 8, 6, 12]

knapsack = [[0 for j in range(K+1)] for i in range(N+1)]

for i in range(1,N+1):
    for j in range(1,K+1):
        if j >= W[i]:
            knapsack[i][j] = max(knapsack[i - 1][j - W[i]] + V[i], knapsack[i - 1][j])
        else:
            knapsack[i][j] = knapsack[i-1][j]
#==결과==
#무게j  0  1  2  3  4   5   6   7   /물품i
    # [[0, 0, 0, 0, 0,  0,  0,  0], W= 0, V =  0
    #  [0, 0, 0, 0, 0,  0, 13, 13], W= 6, V = 13
    #  [0, 0, 0, 0, 8,  8, 13, 13], W= 4, V =  8
    #  [0, 0, 0, 6, 8,  8, 13, 14], W= 3, V =  6
    #  [0, 0, 0, 6, 8, 12, 13, 14]] W= 5, V = 15