Discussion :

[dahtah]

Bonjour a tous,

J'ai le probleme suivant auquel je ne trouve pas de solution optimale. Je cherche a trouver a partir de nombres arbitraires (ie: 1, 3, 6, 7, 14, ...) un nombre final (ie: 21). Je peux seulement ajouter les nombres entres eux, mais les nombres peuvent etre utilises plusieurs fois.

Dans les nombres proposes au dessus, pour trouver 21, je peux faire:

1. 7 + 14 = 21
2. 7 * 3 = 7 + 7 + 7 = 21
3. 3 * 7 = 3 + 3 + 3 + 3 + 3 + 3 + 3 = 21
4. 3 * 2 + 7 * 2 + 1 = 3 + 3 + 7+ 7 + 1 = 21
5. ...

Je cherche a trouver la solution qui implique le moins d'operations d'additions. Les solutions les meilleurs sont dans l'ordre 1, 2, 4, puis 3.

Je vois pas trop comment approcher le probleme. Je pense que c'est une equation a n inconnues (ie: a + 3b +6c + 7d + 14e + ... = 21) ou je n'ai qu'une seule equation et ou chaque variable peut etre nulle. Y'a-t-il un moyen d'essayer de resoudre ca dans certains cas?
J'imagine que s'il y a plusieurs solutions, la solution optimale sera celle ou la somme des variables sera la plus petite, indiquant le moins d'operations.

Merci

PS: Pour ceux que ca interesse, voila comment sont trouves les nombres:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#!/usr/bin/env python
# -*- coding:utf-8 -*-
 
from __future__ import print_function
from elftools.elf.elffile import ELFFile
from elftools.common.exceptions import ELFError, ELFParseError
from struct import unpack, error
from sys import argv, stderr
 
names = (b".text", b".data")
sections = []
segments = []
 
if len(argv) != 3:
	print("Usage: %s filename number" % argv[0])
	exit(-1)
 
try:
	f = open(argv[1], "rb")
except Exception as ex:
	print("Can't open file %s: %s" % (argv[1], ex), file=stderr)
	exit(-1)
 
try:
	elf = ELFFile(f)
except (ELFError, ELFParseError) as ex:
	print("Failed to parse elf file %s: %s" % (argv[1], ex), file=stderr)
	exit(-1)
 
for s in names:
	try:
		section = elf.get_section_by_name(s)
		if section != None:
			sections.append(section)
	except (ELFError, ELFParseError) as ex:
		print("Failed to parse elf file %s: %s" % (argv[1], ex), file=stderr)
 
for segment in elf.iter_segments():
	for section in sections:
		if segment.section_in_segment(section) and (segment["p_type"] == "PT_LOAD"):
			segments.append(segment)
			print("Found loadable segment starting at [address 0x%08x, offset 0x%08x]" %  (segment["p_vaddr"], segment["p_offset"]))
 
candidates = {}
 
for segment in segments:
	segment_data = segment.data()
	for i in xrange(0, len(segment_data)):
		try:
			num = unpack("<I", segment_data[i:i+4])
		except error as se:
			print("Reaching end of segment data. Skipping last bytes...", file=stderr)
		if (num[0] <= int(argv[2])) and (num[0] != 0):
			candidates[segment["p_vaddr"] + i] = num[0]
 
f.close()
 
for k,v in candidates.iteritems():
	print("0x%08x => 0x%08x, %i" % (k, v, v))

et un exemple de sortie:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
dahtah@kali:~$ ./find_numbers.py binary 1234 2> /dev/null | head
Found loadable segment starting at [address 0x08048000, offset 0x00000000]
Found loadable segment starting at [address 0x08049ed0, offset 0x00000ed0]
0x08049f44 => 0x00000014, 20
0x08048203 => 0x00000010, 16
0x08048005 => 0x00000101, 257
0x08048006 => 0x00000001, 1
0x08048a07 => 0x0000004f, 79
0x08048aa8 => 0x00000003, 3
0x08048013 => 0x00000100, 256
0x08048014 => 0x00000001, 1

[dahtah]

Ok, j'avance un peu dans mon probleme. J'arrive a le nommer, c'est deja ca. Il semble que je cherche a resoudre un systeme d'equation lineaire sous-determine (underdetermined system).

J'arrive a resoudre mon probleme en trouvant la meilleure solution avec la methode des moindres carres:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
>>> A = n.array([[1,3,6,7,14]])
>>> b = n.array([21])
>>> n.linalg.lstsq(A,b)
(array([ 0.07216495,  0.21649485,  0.43298969,  0.50515464,  1.01030928]), array([], dtype=float64), 1, array([ 17.05872211]))
>>> 0.07216495 + 0.21649485 * 3 + 0.43298969 * 6 + 0.50515464 * 7 + 1.01030928 * 14
21.00000004

Mais bon, c'est pas ce que je veux. J'ai besoin de l'ensemble des solutions avec des coefficients entiers. Je continue ma recherche...

[bertry]

Salut,

Ok, j'avance un peu dans mon probleme. J'arrive a le nommer, c'est deja ca. Il semble que je cherche a resoudre un systeme d'equation lineaire sous-determine (underdetermined system).

Ton problème me fait plutot penser au Problème du rendu de monaie(Quelles pièces pour faire l'appoint ?)

[dahtah]

Salut,

Ton problème me fait plutot penser au Problème du rendu de monaie(Quelles pièces pour faire l'appoint ?)

Merci pour cet aiguillage, c'etait exactement ca.

Pour info, j'ai pas pu utiliser la methode gloutonne, car je n'arrivais pas au resultat optimal (comme le precise wikipedia). J'ai utilise la methode "dynamic programming", en adaptant des bouts de code honteusement pompes sur le net. Pour ceux que ca interesse, voila la solution au probleme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
def solve_coin_change(coins, change):
    """Coin change problem solver using dynamic programming
       Refer to wikipedia for the description: http://en.wikipedia.org/wiki/Coin_problem
       And to this blog for a nice explanation: http://interactivepython.org/runestone/static/pythonds/Recursion/recursioncomplex.html
       And here fo a half working implementation: http://bryceboe.com/2009/11/04/dynamic-programming-%E2%80%93-coin-change-problem-in-python/
    """
    table = [None for x in xrange(change + 1)]
    table[0] = []
    for i in xrange(1, change + 1):
        for coin in coins:
            length = 0
            if table[i - coin] != None:
              length = len(table[i - coin])
            if coin > i: continue
            elif not table[i] or (length + 1 < len(table[i])):
                if table[i - coin] != None:
                    table[i] = table[i - coin][:]
                    table[i].append(coin)
    return len(table[-1]) if table[-1] != None else 0, table[-1] if table[-1] != None else None
 
val = [1,3,6,7,15]
res = 43
print solve_coin_change(val, res)

Merci encore bertry.