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