J'ai des difficultés à comprendre la programmation dynamique, j'ai donc décidé de résoudre certains problèmes. Je connais des algorithmes dynamiques de base comme la plus longue recherche courante, le problème du knapack, mais je les connais parce que je les lis, mais je ne peux pas venir avec quelque chose de mien: - (
Par exemple, nous avons la recherche de chiffres naturels. Chaque numéro que nous puissions prendre avec plus ou moins. À la fin, nous prenons une valeur absolue de cette somme. Pour chaque ultérieur, trouvez le résultat le plus bas possible.
in1: 10 3 5 4; OUT1: 2
in2: 4 11 5 5 5; OUT2: 0
in3: 10 50 60 65 90 100; OUT3: 5
Explication du 3ème: 5 = | 10 + 50 + 60 + 65-90-100 |
Qu'est-ce qui pire que mon ami m'a dit que c'est un problème de sacs à dos simple, mais je ne peux voir aucun sac à dos ici. La programmation dynamique est-elle difficile ou seulement j'ai de gros problèmes avec cela?
3 Réponses :
C'est le même problème que dans le remorqueur de la guerre, sans la contrainte de tailles d'équipe équilibrées (qui n'est pas pertinente): http://acm.uva.es/p/v100/10032.html
J'avais résolu ce problème avec une approche descendante. Cela fonctionne sur la contrainte qu'il existe une limite supérieure aux nombres donnés. Avez-vous une limite supérieure ou les chiffres sont-ils inconstruits? S'ils sont inconstruits, je ne vois pas comment résoudre cela avec une programmation dynamique.
Pourriez-vous clarifier quelle est cette approche descendante? Les chiffres sont inférieurs à 10000 et il y a moins de 5000 numéros
Je pense que la solution postée par Óscar López est plus élégante que la mienne.
Le sac à dos ici est Votre lié L'idée est - vous voulez maximiser la quantité de chiffres que vous "choisissez" sans passer la limite de Ce problème est en fait le problème de partition , qui est un cas particulier de sous-ensemble sum Problème .
Le problème de la partition dit: "Est-il possible d'obtenir un sous-ensemble des éléments qui résume exactement la moitié?"
poids = valeur = numéro pour chaque élément.
w est 1/2 * somme (éléments) .
1/2 * somme (éléments) , qui est exactement sac à dos avec valeur = Poids .
La dérivation de votre problème d'ici est simple - s'il y en a, prenez-les comme + , et ceux que vous n'avez pas pris comme - et vous obtenez < Code> Out = 0 . [L'inverse autour fonctionne de la même manière]. Ainsi, votre problème décrit est l'optimisation du problème de partition.
Comme il a été souligné par AMIT, cet algorithme peut être compris comme une instance du Problème de partition a>. Pour une implémentation simple, jetez un coup d'œil à ce code Python: partition([10, 50, 60, 65, 90, 100])