如何在固定数量的纸币之间分配价值

huangapple go评论74阅读模式
英文:

How to distribute value between fixed amount of notes

问题

  1. def find_note_combinations():
  2. target_value = 1397
  3. target_count = 512
  4. notes = [200, 100, 50, 20, 10, 5, 2]
  5. notes_count = len(notes)
  6. # Initialize variables to store the current combination
  7. current_combination = [0] * notes_count
  8. while True:
  9. # Calculate the current sum based on the current combination
  10. current_sum = sum(note * count for note, count in zip(notes, current_combination))
  11. # If the current sum matches the target value and the count matches the target count
  12. if current_sum == target_value and sum(current_combination) == target_count:
  13. return current_combination
  14. # Find the rightmost non-maxed out note
  15. index = notes_count - 1
  16. while index >= 0 and current_combination[index] == target_count:
  17. index -= 1
  18. # If all notes are maxed out, no solution is possible
  19. if index == -1:
  20. return None
  21. # Increment the count of the rightmost non-maxed out note
  22. current_combination[index] += 1
  23. # Reset all counts to the right of this note
  24. for i in range(index + 1, notes_count):
  25. current_combination[i] = 0
  26. x1, x2, x3, x4, x5, x6, x7 = find_note_combinations()
  27. print("Number of 200 notes:", x1)
  28. print("Number of 100 notes:", x2)
  29. print("Number of 50 notes:", x3)
  30. print("Number of 20 notes:", x4)
  31. print("Number of 10 notes:", x5)
  32. print("Number of 5 notes:", x6)
  33. print("Number of 2 notes:", x7)

This code efficiently finds a combination of notes that satisfies your conditions without the need for nested loops. It uses a systematic approach to explore possible combinations and returns the result when a valid combination is found.

英文:

I have 512 notes between the values ​​of 200, 100, 50, 20, 10, 5 and 2. The sum of these notes ​​is exactly 1397. How much of each note do I have with none of them being 0?

Answer:

  • 200: 1 note
  • 100: 1 note
  • 50: 1 note
  • 20: 1 note
  • 10: 1 note
  • 5: 1 note
  • 2: 506 notes

I know there are several possibilities, how I can write a algorithm who return at least one solution for any number of notes and any sum of values? I need to make an code in Python. Thanks!

EDIT: Thanks to Kelly Bundy in the comments, it turns out I'm trying to find an impossible solution with my bad example. So, with the comment edited, I arrived at this code:

  1. def find_note_combinations():
  2. for x1 in range(1, 513):
  3. for x2 in range(1, 513):
  4. for x3 in range(1, 513):
  5. for x4 in range(1, 513):
  6. for x5 in range(1, 513):
  7. for x6 in range(1, 513):
  8. for x7 in range(1, 513):
  9. if x1 + x2 + x3 + x4 + x5 + x6 + x7 == 512 and 200 * x1 + 100 * x2 + 50 * x3 + 20 * x4 + 10 * x5 + 5 * x6 + 2 * x7 == 1397:
  10. return x1, x2, x3, x4, x5, x6, x7
  11. x1, x2, x3, x4, x5, x6, x7 = find_note_combinations()
  12. print("Number of 200 notes:", x1)
  13. print("Number of 100 notes:", x2)
  14. print("Number of 50 notes:", x3)
  15. print("Number of 20 notes:", x4)
  16. print("Number of 10 notes:", x5)
  17. print("Number of 5 notes:", x6)
  18. print("Number of 2 notes:", x7)

But it's ugly and inefficient, help?

答案1

得分: 2

以下是代码的翻译部分:

  1. # 笔记字典(至少要有每个值为1的)
  2. notes = [
  3. [2, 1],
  4. [5, 1],
  5. [10, 1],
  6. [20, 1],
  7. [50, 1],
  8. [100, 1],
  9. [200, 1],
  10. ]
  11. def find_solution(target, amount, notes):
  12. s = sum(n * a for n, a in notes)
  13. if amount == 0 and s == target:
  14. return True
  15. if s > target or amount < 0:
  16. return False
  17. for i in range(len(notes)):
  18. notes[i][1] += 1
  19. if find_solution(target, amount - 1, notes):
  20. return True
  21. notes[i][1] -= 1
  22. return False
  23. if find_solution(1397, 512 - len(notes), notes):
  24. print(notes)

打印:

  1. [[2, 506], [5, 1], [10, 1], [20, 1], [50, 1], [100, 1], [200, 1]]

编辑:添加一些启发式方法:

  1. from itertools import product
  2. notes = [
  3. [2, 1],
  4. [5, 1],
  5. [10, 1],
  6. [20, 1],
  7. [50, 1],
  8. [100, 1],
  9. [200, 1],
  10. ]
  11. def find_solution(target, amount, notes):
  12. global steps
  13. steps += 1
  14. if steps > 1_000_000:
  15. return False
  16. s = sum(n * a for n, a in notes)
  17. if amount == len(notes):
  18. if target - s not in amount_shorcut:
  19. return False
  20. else:
  21. for val in amount_shorcut[target - s]:
  22. for i in range(len(notes)):
  23. if notes[i][0] == val:
  24. notes[i][1] += 1
  25. break
  26. return True
  27. if amount == 0 and s == target:
  28. return True
  29. if s >= target or amount <= 0:
  30. return False
  31. for i in range(len(notes)):
  32. notes[i][1] += 1
  33. if find_solution(target, amount - 1, notes):
  34. return True
  35. notes[i][1] -= 1
  36. return False
  37. amount_shorcut = {}
  38. for t in product([n for n, _ in notes], repeat=len(notes)):
  39. amount_shorcut[sum(t)] = t
  40. AMOUNT = 12345
  41. N = 87
  42. notes = sorted(notes, key=lambda l: abs(l[0] - (AMOUNT / N)))
  43. # 步骤1:
  44. steps = 0
  45. if find_solution(AMOUNT, N - len(notes), notes):
  46. print(notes)
  47. else:
  48. # 步骤2(交换前两个钞票):
  49. steps = 0
  50. notes[0], notes[1] = notes[1], notes[0]
  51. if find_solution(AMOUNT, N - len(notes), notes):
  52. print(notes)
  53. print('总步数:', steps)

这将打印:

  1. [[200, 60], [100, 2], [50, 1], [20, 2], [10, 1], [5, 1], [2, 20]]
  2. 总步数:60434
英文:

You can use a recursion for the task (I recommend to sort the notes array from lower bill to bigger one):

  1. # notes dict (we must have 1 of each at minimum)
  2. notes = [
  3. [2, 1],
  4. [5, 1],
  5. [10, 1],
  6. [20, 1],
  7. [50, 1],
  8. [100, 1],
  9. [200, 1],
  10. ]
  11. def find_solution(target, amount, notes):
  12. s = sum(n * a for n, a in notes)
  13. if amount == 0 and s == target:
  14. return True
  15. if s &gt; target or amount &lt; 0:
  16. return False
  17. for i in range(len(notes)):
  18. notes[i][1] += 1
  19. if find_solution(target, amount - 1, notes):
  20. return True
  21. notes[i][1] -= 1
  22. return False
  23. if find_solution(1397, 512 - len(notes), notes):
  24. print(notes)

Prints:

  1. [[2, 506], [5, 1], [10, 1], [20, 1], [50, 1], [100, 1], [200, 1]]

EDIT: Adding some heurestics:

  1. from itertools import product
  2. notes = [
  3. [2, 1],
  4. [5, 1],
  5. [10, 1],
  6. [20, 1],
  7. [50, 1],
  8. [100, 1],
  9. [200, 1],
  10. ]
  11. def find_solution(target, amount, notes):
  12. global steps
  13. steps += 1
  14. if steps &gt; 1_000_000:
  15. return False
  16. s = sum(n * a for n, a in notes)
  17. if amount == len(notes):
  18. if target - s not in amount_shorcut:
  19. return False
  20. else:
  21. for val in amount_shorcut[target - s]:
  22. for i in range(len(notes)):
  23. if notes[i][0] == val:
  24. notes[i][1] += 1
  25. break
  26. return True
  27. if amount == 0 and s == target:
  28. return True
  29. if s &gt;= target or amount &lt;= 0:
  30. return False
  31. for i in range(len(notes)):
  32. notes[i][1] += 1
  33. if find_solution(target, amount - 1, notes):
  34. return True
  35. notes[i][1] -= 1
  36. return False
  37. amount_shorcut = {}
  38. for t in product([n for n, _ in notes], repeat=len(notes)):
  39. amount_shorcut[sum(t)] = t
  40. AMOUNT = 12345
  41. N = 87
  42. notes = sorted(notes, key=lambda l: abs(l[0] - (AMOUNT / N)))
  43. # step 1:
  44. steps = 0
  45. if find_solution(AMOUNT, N - len(notes), notes):
  46. print(notes)
  47. else:
  48. # step 2 (swap first two bills):
  49. steps = 0
  50. notes[0], notes[1] = notes[1], notes[0]
  51. if find_solution(AMOUNT, N - len(notes), notes):
  52. print(notes)
  53. print(&#39;Total amount of steps:&#39;, steps)

This prints:

  1. [[200, 60], [100, 2], [50, 1], [20, 2], [10, 1], [5, 1], [2, 20]]
  2. Total amount of steps: 60434

huangapple
  • 本文由 发表于 2023年6月16日 06:11:09
  • 转载请务必保留本文链接:https://go.coder-hub.com/76485816.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定