---
# System prepended metadata

title: TP3 - Programmation dynamique

---

# TP3 - Programmation dynamique



## Limite du programme

Notre programme permet de résoudre le problème mais lorsqu'une pièce `x` est égale à l'objectif, le programme retourne la solution `[x, 0]` au lieu de `[x]`. Nous n'avons pas réussi à trouver l'origine du problème.

## Programme
```python
import math
import numpy as np
import itertools
import pdb
import pandas

def computeTarget(coins):
    S = sum(coins)
    target = S // 2
    return (S, target)

def printMatrix(matrix, coins):
    (S, target) = computeTarget(coins)
    dataFrame = pandas.DataFrame(matrix, index = list(range(1, len(coins) + 1)), columns = list(range(1, target + 1)))
    print(dataFrame)

def findSol(res, coins, lastLine, goal):
  solutions = []

  # Find first true col in the last row
  index=0

  for i in range(goal-1, -1, -1):
    if res[lastLine][i]:
      index = i
      break

  # We found the last coin that was correct
  for i in range(lastLine, -1, -1):
    if index == 0:
        break
    if i == 0:
      solutions.append(index+1)
      break

    if res[i][index] and not res[i-1][index]:
      solutions.append(coins[i])
      index=index-coins[i]

  return solutions

def divByTwo(coins):
  goal = sum(coins) // 2

  res = np.full((len(coins), goal), False)
  np.set_printoptions(threshold=np.nan)

  lastLine=len(coins)-1
  for line in range(0, len(coins)):

    if line == 0:
      res[line][coins[0]-1] = True
      continue

    res[line] = res[line-1]

    for i in range(goal):
      if res[line][i] and res[line-1][i]:
        if i+1+coins[line] > goal:
          break
        res[line][i+coins[line]] = True


    if coins[line] <= goal:
      res[line][coins[line]-1] = True

    if res[line][goal-1]:
      lastLine=line
      break

  solutions = findSol(res, coins, lastLine, goal)

  printMatrix(res, coins)
  print(solutions)

def main():
  coins = [5,3,17,7,11,9]
  divByTwo(coins)

main()
```