使用两个参数的动态规划：天数和优惠券。

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

Dynamic programming with two parameters: days and coupons

问题

有一家咖啡馆有以下的折扣系统：每次购买金额超过100美元，买家将获得一张免费午餐的优惠券。
你有一个未来N天的价格列表，如下所示：

  1. 5
  2. 35
  3. 40
  4. 101
  5. 59
  6. 63

价格限制：0 ≤ 价格 ≤ 300

找出午餐的最小总成本以及应该使用优惠券的天数。

请帮忙完善DP（动态规划）的实现。我不确定初始的DP表是否适合这个任务，所以无法正确处理边界情况。

谢谢。

更新：扩展的解决方案似乎可以获得最佳结果，但未被第三方测试系统接受：

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math"
  6. 	"os"
  7. 	"sort"
  8. 	"strconv"
  9. 	"strings"
  10. )
  12. func main() {
  13. 	file, _ := os.ReadFile("input.txt")
  15. 	lines := strings.Split(string(file), "\n")
  17. 	p := make([]int, 0, len(lines))
  19. 	for i := 1; i < len(lines); i++ {
  20. 		price, err := strconv.Atoi(lines[i])
  22. 		if err != nil {
  23. 			continue
  24. 		}
  26. 		p = append(p, price)
  27. 	}
  29. 	l := len(p)
  31. 	dp := make([][]int, l+1)
  32. 	dp[0] = make([]int, len(dp))
  34. 	for i := 1; i < len(dp); i++ {
  35. 		dp[0][i] = math.MaxInt32
  36. 	}
  38. 	for i := 1; i < len(dp); i++ {
  39. 		dp[i] = make([]int, l+1)
  40. 	}
  42. 	// 填充dp
  43. 	for i := 1; i <= l; i++ {
  44. 		for j := 0; j <= l; j++ {
  45. 			if p[i-1] <= 100 {
  46. 				if j == l {
  47. 					dp[i][j] = MinOrZero(dp[i-1][j]+p[i-1], dp[i-1][j])
  48. 					continue
  49. 				}
  51. 				dp[i][j] = MinOrZero(dp[i-1][j]+p[i-1], dp[i-1][j+1])
  52. 				continue
  53. 			}
  55. 			if j == 0 {
  56. 				dp[i][j] = MinOrZero(math.MaxInt32, dp[i-1][j+1])
  57. 				continue
  58. 			}
  60. 			if j == l {
  61. 				dp[i][j] = MinOrZero(dp[i-1][j-1]+p[i-1], dp[i-1][j])
  62. 				continue
  63. 			}
  65. 			dp[i][j] = MinOrZero(dp[i-1][j-1]+p[i-1], dp[i-1][j+1])
  66. 		}
  67. 	}
  69. 	// 剩余的优惠券
  70. 	coupons := 0
  71. 	min := math.MaxInt
  73. 	for j := l; j >= 0; j-- {
  74. 		sum := dp[l][j]
  76. 		if sum < min {
  77. 			min = sum
  78. 			coupons = j
  79. 		}
  80. 	}
  82. 	couponDays := make([]int, 0)
  83. 	j := coupons
  84. 	sum := min
  86. 	for i := l; i > 0; i-- {
  87. 		jl := j - 1
  88. 		js := j
  89. 		jr := j + 1
  91. 		if jr < l && dp[i-1][jr] == sum {
  92. 			couponDays = append(couponDays, i)
  93. 			j++
  94. 			continue
  95. 		}
  97. 		if dp[i-1][js] == sum {
  98. 			sum = dp[i-1][js]
  99. 			continue
  100. 		}
  102. 		if jl >= 0 && dp[i-1][jl] == sum-p[i-1] {
  103. 			sum = dp[i-1][jl]
  104. 			j--
  105. 			continue
  106. 		}
  108. 		sum -= p[i-1]
  109. 	}
  111. 	sort.Ints(couponDays)
  113. 	fmt.Println(min)
  114. 	fmt.Println(fmt.Sprintf("%d %d", coupons, len(couponDays)))
  115. 	for _, day := range couponDays {
  116. 		fmt.Println(day)
  117. 	}
  118. }
  120. func Min(i, j int) int {
  121. 	if i <= j {
  122. 		return i
  123. 	}
  125. 	return j
  126. }
  128. func MinOrZero(i, j int) int {
  129. 	var result int
  131. 	if i <= j {
  132. 		result = i
  133. 	} else {
  134. 		result = j
  135. 	}
  137. 	if result >= 0 {
  138. 		return result
  139. 	}
  141. 	return 0
  142. }

输入数据测试失败，并且答案应该是。

英文:

There is a cafe that has the following discount system: for each purchase of more than $100, the buyer receives a coupon that gives the right to one free lunch.
You have a price list for the next N days like:

  1. 5
  2. 35
  3. 40
  4. 101
  5. 59
  6. 63

The price limitation: 0 ≤ price ≤ 300

Find the minimum possible total cost of lunches and the numbers of days on which you should use the coupons.

Please help to stabilize DP fulfilling. I am not sure the initial DP table is suitable for the task so I can not handle edge cases correctly:

  1. func main() {
  2. file, _ := os.ReadFile(&quot;input.txt&quot;)
  3. lines := strings.Split(string(file), &quot;\n&quot;)
  4. p := make([]int, 0, len(lines))
  5. for i := 0; i &lt; len(lines); i++ {
  6. price, err := strconv.Atoi(lines[i])
  7. if err != nil {
  8. continue
  9. }
  10. p = append(p, price)
  11. }
  12. dp := make([][]int, len(p)+1)
  13. dp[0] = make([]int, len(dp))
  14. // zero day row
  15. for i := 1; i &lt; len(dp); i++ {
  16. // no coupons on the first day visit
  17. dp[0][i] = math.MaxInt32
  18. }
  19. // 1...N days
  20. for i := 1; i &lt; len(dp); i++ {
  21. dp[i] = make([]int, len(p))
  22. }
  23. for i := 1; i &lt;= len(p); i++ {
  24. for j := 0; j &lt; len(p); j++ {
  25. if p[i-1] &lt;= 100 {
  26. dp[i][j] = Min(dp[i-1][j]+p[i-1], dp[i-1][j+1])
  27. }
  28. dp[i][j] = Min(dp[i-1][j-1]+p[i-1], dp[i-1][j+1])
  29. }
  30. }
  31. fmt.Println(dp)
  32. }
  33. func Min(i, j int) int {
  34. if i &lt;= j {
  35. return i
  36. }
  37. return j
  38. }

Thank you.

Upd. Extended solution which seems to achieve the best results but is unaccepted by 3rt party testing system:

  1. package main
  2. import (
  3. &quot;fmt&quot;
  4. &quot;math&quot;
  5. &quot;os&quot;
  6. &quot;sort&quot;
  7. &quot;strconv&quot;
  8. &quot;strings&quot;
  9. )
  10. func main() {
  11. file, _ := os.ReadFile(&quot;input.txt&quot;)
  12. lines := strings.Split(string(file), &quot;\n&quot;)
  13. p := make([]int, 0, len(lines))
  14. for i := 1; i &lt; len(lines); i++ {
  15. price, err := strconv.Atoi(lines[i])
  16. if err != nil {
  17. continue
  18. }
  19. p = append(p, price)
  20. }
  21. l := len(p)
  22. dp := make([][]int, l+1)
  23. dp[0] = make([]int, len(dp))
  24. for i := 1; i &lt; len(dp); i++ {
  25. dp[0][i] = math.MaxInt32
  26. }
  27. for i := 1; i &lt; len(dp); i++ {
  28. dp[i] = make([]int, l+1)
  29. }
  30. // fill dp
  31. for i := 1; i &lt;= l; i++ {
  32. for j := 0; j &lt;= l; j++ {
  33. if p[i-1] &lt;= 100 {
  34. if j == l {
  35. dp[i][j] = MinOrZero(dp[i-1][j]+p[i-1], dp[i-1][j])
  36. continue
  37. }
  38. dp[i][j] = MinOrZero(dp[i-1][j]+p[i-1], dp[i-1][j+1])
  39. continue
  40. }
  41. if j == 0 {
  42. dp[i][j] = MinOrZero(math.MaxInt32, dp[i-1][j+1])
  43. continue
  44. }
  45. if j == l {
  46. dp[i][j] = MinOrZero(dp[i-1][j-1]+p[i-1], dp[i-1][j])
  47. continue
  48. }
  49. dp[i][j] = MinOrZero(dp[i-1][j-1]+p[i-1], dp[i-1][j+1])
  50. }
  51. }
  52. // coupons left
  53. coupons := 0
  54. min := math.MaxInt
  55. for j := l; j &gt;= 0; j-- {
  56. sum := dp[l][j]
  57. if sum &lt; min {
  58. min = sum
  59. coupons = j
  60. }
  61. }
  62. couponDays := make([]int, 0)
  63. j := coupons
  64. sum := min
  65. for i := l; i &gt; 0; i-- {
  66. jl := j - 1
  67. js := j
  68. jr := j + 1
  69. if jr &lt; l &amp;&amp; dp[i-1][jr] == sum {
  70. couponDays = append(couponDays, i)
  71. j++
  72. continue
  73. }
  74. if dp[i-1][js] == sum {
  75. sum = dp[i-1][js]
  76. continue
  77. }
  78. if jl &gt;= 0 &amp;&amp; dp[i-1][jl] == sum-p[i-1] {
  79. sum = dp[i-1][jl]
  80. j--
  81. continue
  82. }
  83. sum -= p[i-1]
  84. }
  85. sort.Ints(couponDays)
  86. fmt.Println(min)
  87. fmt.Println(fmt.Sprintf(&quot;%d %d&quot;, coupons, len(couponDays)))
  88. for _, day := range couponDays {
  89. fmt.Println(day)
  90. }
  91. }
  92. func Min(i, j int) int {
  93. if i &lt;= j {
  94. return i
  95. }
  96. return j
  97. }
  98. func MinOrZero(i, j int) int {
  99. var result int
  100. if i &lt;= j {
  101. result = i
  102. } else {
  103. result = j
  104. }
  105. if result &gt;= 0 {
  106. return result
  107. }
  108. return 0
  109. }

Input data test fails on. And the answer should be.

答案1

得分: 1

为了能够返回使用优惠券的日期，您需要跟踪最佳路径，然后在最后可以向后遍历。

当使用或获得车票时，您必须非常小心，因为它会改变dp数组中的位置。某些位置可能保持未定义。例如，如果您在第一天获得一张车票，那么对应于0张车票的单元格将保持未定义，因为当天的成本被放在1张车票上（如果价格超过100，第二天我们会得到0张或2张车票，但不是1张）。如果正确地进行上下跳跃，它应该可以工作。

以下是翻译好的代码部分：

  1. function solve(prices) {
  2.   const dp = [[]], n = prices.length
  3.   let tickets = prices[0] > 100 ? 1 : 0
  4.   dp[0][tickets] = {cost: prices[0]}
  5.   for (let i = 1; i < n; i++) {
  6.     dp.push([])
  7.     let t = prices[i] > 100 ? 1 : 0
  8.     // not using tickets
  9.     for (let j = 0; j <= tickets; j++)
  10.       if (dp[i - 1][j])
  11.         dp[i][j + t] = {cost: dp[i - 1][j].cost + prices[i], prev: j}
  12.     // using tickets
  13.     for (let j = 1; j <= tickets; j++)
  14.       if (dp[i - 1][j] && (!dp[i][j - 1] || dp[i][j - 1].cost > dp[i - 1][j].cost))
  15.         dp[i][j - 1] = {cost: dp[i - 1][j].cost, prev: j}
  16.     tickets += t
  17.   }
  18.   // min has to be at 0 or 1 ticket
  19.   let idx = dp[n - 1][0] && (!dp[n - 1][1] || dp[n - 1][0].cost <= dp[n - 1][1].cost) ? 0 : 1
  20.   console.log('costs: ' + dp[n - 1][idx].cost)
  21.   const days = []
  22.   for (let day = n - 1; day > 0; day--) {
  23.     if (dp[day][idx].prev > idx)
  24.       days.unshift(day)
  25.     idx = dp[day][idx].prev
  26.   }
  27.   console.log('days: ' + days)
  28. }
  30. solve([88,55,101,77,44,130,160,22,55,97,101,2,88])

希望对您有所帮助！

英文:

To be able to return the days on which the coupons were used you need to keep track of the best path and then you can go backwards at the end.

You have to be very careful when tickets are used or gained because it shifts the position in the dp array. Some positions can stay undefined. E.g. if you get a ticket on the first day then the cell corresponding to 0 tickets stays undefined, because the costs for the day are put at 1 tickets (and if the price is above 100 the next day we end up with 0 or 2 tickets, but not with 1). If that jumping up and down is done correctly it should work.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. function solve(prices) {
  2. const dp = [[]], n = prices.length
  3. let tickets = prices[0] &gt; 100 ? 1 : 0
  4. dp[0][tickets] = {cost: prices[0]}
  5. for (let i = 1; i &lt; n; i++) {
  6. dp.push([])
  7. let t = prices[i] &gt; 100 ? 1 : 0
  8. // not using tickets
  9. for (let j = 0; j &lt;= tickets; j++)
  10. if (dp[i - 1][j])
  11. dp[i][j + t] = {cost: dp[i - 1][j].cost + prices[i], prev: j}
  12. // using tickets
  13. for (let j = 1; j &lt;= tickets; j++)
  14. if (dp[i - 1][j] &amp;&amp; (!dp[i][j - 1] || dp[i][j - 1].cost &gt; dp[i - 1][j].cost))
  15. dp[i][j - 1] = {cost: dp[i - 1][j].cost, prev: j}
  16. tickets += t
  17. }
  18. // min has to be at 0 or 1 ticket
  19. let idx = dp[n - 1][0] &amp;&amp; (!dp[n - 1][1] || dp[n - 1][0].cost &lt;= dp[n - 1][1].cost) ? 0 : 1
  20. console.log(&#39;costs: &#39; + dp[n - 1][idx].cost)
  21. const days = []
  22. for (let day = n - 1; day &gt; 0; day--) {
  23. if (dp[day][idx].prev &gt; idx)
  24. days.unshift(day)
  25. idx = dp[day][idx].prev
  26. }
  27. console.log(&#39;days: &#39; + days)
  28. }
  29. solve([88,55,101,77,44,130,160,22,55,97,101,2,88])

<!-- end snippet -->

huangapple
  • 本文由 发表于 2023年3月2日 02:39:53
  • 转载请务必保留本文链接：https://go.coder-hub.com/75607715.html
  • algorithm
  • dynamic-programming
  • go
匿名

发表评论

匿名网友

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

确定