Eight step procedures - Revision history

Fall2024 Team 22 Wiki: /* Algorithm Discussion */ & citations

2024-12-16T00:53:08Z

Algorithm Discussion: & citations

← Older revision		Revision as of 20:53, 15 December 2024
Line 12:		Line 12:
	=Algorithm Discussion=		=Algorithm Discussion=

	When tackling a dynamic programming problem, there are generally a number of key steps to follow. The first and most crucial step is determining whether dynamic programming is the right approach. A key indicator of this is whether the problem can be broken down into smaller, overlapping subproblems. Problems that involve minimizing or maximizing a quantity, or those that require counting possible arrangements, are often strong candidates for dynamic programming solutions.<ref name=":0">Benjaminson, E. (2023, January). A Framework for Solving Dynamic Programming Problems. Github.io. sassafras13.github.io/SolvingDPProblems/. </ref>		When tackling a dynamic programming problem, there are generally a number of key steps to follow. The first and most crucial step is determining whether dynamic programming is the right approach. A key indicator of this is whether the problem can be broken down into smaller, overlapping subproblems. Problems that involve minimizing or maximizing a quantity, or those that require counting possible arrangements, are often strong candidates for dynamic programming solutions.<ref name=":0">Benjaminson, E. (2023, January). A Framework for Solving Dynamic Programming Problems. Github.io. sassafras13.github.io/SolvingDPProblems/. </ref> For example, in the Fibonacci sequence:

	~~Once you’ve identified that dynamic programming is applicable~~, ~~the next step is to identify the variables involved~~, particularly those that change as the subproblems are solved. These changing variables are critical to breaking the problem down into manageable pieces. To identify the key variables, it can be helpful to list out a few examples of subproblems and compare the parameters in each case. By analyzing which parameters vary between subproblems, you can determine the number of subproblems that need to be solved, which will guide the design of the solution.		F(n)=F(n−1)+F(n−2),F(0)=0,F(1)=1

	The third step is to define the recurrence relation, which expresses how the solution to a larger subproblem can be constructed from solutions to smaller subproblems. The recurrence relation serves as the core of the dynamic programming approach, describing how to combine the results of smaller subproblems to build up the final solution.<ref>Luu, H. (2020, November). Dissecting Dynamic ~~Programming – Top down & Bottom Up. Medium. hien-luu.medium.com/dissecting-dynamic-~~programming~~-top-down-bottom-up-3d3a1d62fbd7. </ref> This relation is crucial because it provides~~ the ~~blueprint for how an optimal solution can be derived from~~ previously computed values. It must be carefully defined to ensure that the solution builds progressively and efficiently. Once the recurrence relation is established, the next step is to identify the base cases. Base cases often represent the simplest, smallest possible inputs for which the solution is trivial or already known.<ref name=":0" /> For example, in a problem like Fibonacci number calculation, the base cases are typically the first two numbers of the sequence. Base cases are essential because they serve as the foundation for building up solutions ~~to more complex subproblems. They also act as stopping conditions for the recursion or termination conditions for the iterative approach, ensuring that the algorithm does not run indefinitely~~.		Dynamic programming reduces the time complexity by reusing previously computed solutions.

	~~The next decision is whether to implement a recursive or an iterative solution~~, ~~which corresponds to~~ the ~~choice~~ between ~~a top-down (memoization) approach and a bottom-up (tabulation) approach. In a top-down approach~~, ~~recursion is used to break~~ the problem ~~into smaller subproblems, with results stored in~~ a cache (or memoization table) to avoid redundant calculations.<ref name=":0" /> This approach is typically easier to conceptualize and implement but can lead to stack overflow issues for deep recursions in some languages. In contrast, the bottom-up approach builds the solution iteratively, solving smaller subproblems ~~first~~ and progressively solving larger ones. This method tends to be more efficient in terms of space because it does not require the overhead of recursion but might be harder to understand initially. Both methods ultimately achieve the same goal, and the choice often depends on the specific problem and the programmer's preference.		Next, identify the key variables that change between subproblems, as they are crucial for breaking the problem down. listing a few subproblems and comparing their parameters helps which variables vary.

	The ~~next~~ step is to ~~incorporate memoization (if using~~ the ~~top-down approach) or tabulation (for~~ the ~~bottom-up~~ approach~~). Memoization improves performance by storing~~ the results of ~~expensive function calls so that they don’t need~~ to ~~be recomputed~~.<ref ~~name=":0"~~ /> ~~When a subproblem is solved for the first time~~, ~~its result is stored~~ in ~~a table or dictionary. If~~ the ~~same subproblem needs to be solved again,~~ the ~~stored result~~ is ~~returned instead of recalculating it. This prevents redundant work, leading to significant time savings, particularly for problems with overlapping subproblems.~~		The third step is to define the recurrence relation, which expresses how the solution to a larger subproblem can be constructed from solutions to smaller subproblems. The recurrence relation serves as the core of the dynamic programming approach, describing how to combine the results of smaller subproblems to build up the final solution.<ref>Luu, H. (2020, November). Dissecting Dynamic Programming – Top down & Bottom Up. Medium. hien-luu.medium.com/dissecting-dynamic-programming-top-down-bottom-up-3d3a1d62fbd7. </ref> For example, in the Fibonacci number calculation the recurrence relation is given by:

	~~Finally~~, ~~once you have implemented~~ memoization (or tabulation), the ~~last step is~~ to ~~analyze~~ the time ~~complexity of your solution~~. ~~In dynamic programming~~, the time complexity ~~is determined by two factors:~~ the number of unique subproblems ~~that must be solved,~~ and the time ~~required~~ to solve each ~~subproblem~~. The number of ~~unique~~ subproblems is determined by the ~~number of~~ distinct states defined by the changing parameters, ~~while~~ the ~~time~~ complexity per subproblem ~~typically~~ depends on the ~~amount of~~ work required to compute each solution. ~~By carefully counting~~ the ~~number of subproblems and the cost of solving each one, you can estimate the overall~~ time complexity ~~of your dynamic programming solution. Often, dynamic~~ programming ~~solutions reduce the~~ time complexity from exponential to polynomial time, making otherwise intractable problems solvable.		F(n)=F(n−1)+F(n−2)

			Once this is done, the next step is to identify the base cases which represent the simplest, smallest possible inputs for which the solution is trivial or already known.<ref name=":0" /> The base cases for the Fibonacci sequence are defined as:

			F(0)=0,F(1)=1

			Base cases are essential because they serve as the foundation for building up solutions to more complex subproblems. They also act as stopping conditions for the recursion or termination conditions for the iterative approach, ensuring that the algorithm does not run indefinitely.

			The following decision is whether to use a recursive (top-down, memoization) or iterative (bottom-up, tabulation) approach. The top-down approach uses recursion and caches results to avoid redundant calculations, but can lead to stack overflow with deep recursions. The bottom-up approach solves subproblems iteratively, saving space but being harder to understand initially. Both achieve the same goal.

			Next, implement memoization (top-down) or tabulation (bottom-up). Memoization stores results of expensive function calls in a table or dictionary, returning the stored result for repeated subproblems to avoid redundant calculations. <ref name=":0" /> Letting f(x) represent the solution to a subproblem, the first time f(x) is computed the results are stored in a table or cache T. For subsequent calls with the same input, the result is retrieved from the cache, T(x).

			f(x) = { compute and store result in T(x) if f(x) is not already cached

			f(x) = { T(x) if f(x) is cached }

			This approach avoids redundant calculations, improving performance, especially for problems with overlapping subproblems.

			Finally, the time complexity depends on the number of unique subproblems ''N'' and the time to solve each, T(x). The number of subproblems is determined by the distinct states defined by the changing parameters, and the complexity per subproblem depends on the work required to compute each solution.

			Thus the total time complexity is:

			T<sub>total</sub> = N x T(x)

			Dynamic programming often reduces time complexity from exponential to polynomial time, making otherwise intractable problems solvable.

	=Numerical Examples=		=Numerical Examples=
Line 664:		Line 688:
	'''''Bus Route Selection'''''		'''''Bus Route Selection'''''

	According to a study by engineering students Zhu Wenfei and LI Runmei, dynamic programming is the backbone of creating the most effective path for public transportation, for both the passengers and the city. The study focused on maximizing profit for the bus carriers and passengers, simultaneously. Though factors like distance between stops, average load factor, bus capacity and others are complex, these all affect how the bus operates most efficiently. Furthermore, these factors help form constraints included in models for passenger flow, passenger “satisfaction,” and bus scheduling and speed. Employing the process seen in the examples above, they determined that optimal intervals (Figure 1) where the bus can be most cost effective and useful for civilians. With a 40/60 weight on the two parties in the objective function, the optimization results show a very small decrease in satisfaction for the bus carriers, while a substantial increase for the passengers.		According to a study by engineering students Zhu Wenfei and LI Runmei, dynamic programming is the backbone of creating the most effective path for public transportation, for both the passengers and the city. The study focused on maximizing profit for the bus carriers and passengers, simultaneously. Though factors like distance between stops, average load factor, bus capacity and others are complex, these all affect how the bus operates most efficiently. Furthermore, these factors help form constraints included in models for passenger flow, passenger “satisfaction,” and bus scheduling and speed.<ref name=":1">Zhu, W and Li, R. (2014). Research on dynamic timetables of bus scheduling based on dynamic programming. Chinese Control Conference, pp. 8930-8934.</ref> Employing the process seen in the examples above, they determined that optimal intervals (Figure 1) where the bus can be most cost effective and useful for civilians.<ref name=":1" /> With a 40/60 weight on the two parties in the objective function, the optimization results show a very small decrease in satisfaction for the bus carriers, while a substantial increase for the passengers.
	[[File:Wiki - Dynamic Programming.docx.jpg\|center\|thumb\|433x433px\|A screenshot of final results from employing the method described above and indicating an improvement from current methods. ]]		[[File:Wiki - Dynamic Programming.docx.jpg\|center\|thumb\|433x433px\|A screenshot of final results from employing the method described above and indicating an improvement from current methods.<ref name=":1" /> ]]
	'''''Hybrid Vehicle Optimization'''''		'''''Hybrid Vehicle Optimization'''''

	Because of how many variables are present in vehicle dynamics, it is certainly a prime application for dynamic programming. Specifically, there are unique objective functions for all types of vehicles due to their range in purpose. Lukic and Wang’s study on hybrid engine performance simulated a vehicle's configuration and how a set of parameters affected fuel consumption. For example, the effect of vehicle mass, planetary gear ratios, frontal surface area, maximum battery capacity, and few others were all evaluated to maximize the fuel economy (Wang and Lukic).		Because of how many variables are present in vehicle dynamics, it is certainly a prime application for dynamic programming. Specifically, there are unique objective functions for all types of vehicles due to their range in purpose. Lukic and Wang’s study on hybrid engine performance simulated a vehicle's configuration and how a set of parameters affected fuel consumption. For example, the effect of vehicle mass, planetary gear ratios, frontal surface area, maximum battery capacity, and few others were all evaluated to maximize the fuel economy.<ref name=":2">Wang, R and Lukic, S, M. (2012). Dynamic programming technique in hybrid electric vehicle optimization. IEEE International Electric Vehicle Conference, pp. 1-8.</ref> In doing so, it was found that having a state of charge (SOC) at the initial condition that was slightly higher, while simultaneously discouraging the utilization of the engine on/off feature, would result in the best combination of parameters for gas mileage in the test for PHEVs (plug-in hybrid electric vehicle).<ref name=":2" /> Overall, this method of including multiple parameters and evaluating them for a solution worked again for this set of constraints and single objective function
	[[File:Wiki - Dynamic Programming.docx (1).jpg\|center\|thumb\|468x468px\|A results table from Lukic and Wang’s study that shows the optimal values of 0.9 and 0.5 for most optimal for best fuel economy.]]		[[File:Wiki - Dynamic Programming.docx (1).jpg\|center\|thumb\|468x468px\|A results table from Lukic and Wang’s study that shows the optimal values of 0.9 and 0.5 for most optimal for best fuel economy.<ref name=":2" />]]

	=Conclusion=		=Conclusion=

Fall2024 Team 22 Wiki: Citations

2024-12-15T22:49:45Z

Citations

← Older revision		Revision as of 18:49, 15 December 2024
Line 4:		Line 4:

	=Introduction=		=Introduction=
	In an attempt to innovate new ways for solving the world’s issues, scientists and mathematicians came together years ago to push forward with new ideas. After some time and iteration, dynamic programming (DP) was born –– a complex mathematical optimization method that aims to solve a wide range of problems. Dynamic programming is best used when the problem can be divided into subproblems that are solved until a globally optimal solution is reached. Considering all of this, it is important to highlight that Richard Bellman pushed hard for advancements in the early stages and can be credited with the development of dynamic programming.		In an attempt to innovate new ways for solving the world’s issues, scientists and mathematicians came together years ago to push forward with new ideas. After some time and iteration, dynamic programming (DP) was born –– a complex mathematical optimization method that aims to solve a wide range of problems. Dynamic programming is best used when the problem can be divided into subproblems that are solved until a globally optimal solution is reached. This comes with a small caveat from Sean Eddy claiming, dynamic programming is “guaranteed to give you a mathematically optimal (highest scoring) solution,” but it matters most how the data is scored<ref>Eddy, S. (2004, July). What is dynamic programming?. Nature Biotechnology. <nowiki>https://doi.org/10.1038/nbt0704-909</nowiki>. </ref>. Considering all of this, it is important to highlight that Richard Bellman pushed hard for advancements in the early stages and can be credited with the development of dynamic programming.

	As mentioned, Richard Bellman – a well renowned Stanford professor that was contracting for a non-profit research institution at the time – founded monumental principles on dynamic programming beginning in the 1950s when he started publishing formal work on the topic. In his first publishing, Bellman was forced to strategically name the new computational method due to political condemnation. To avoid using words like “research” and “mathematical,” Bellman sought to emphasize the time-varying and incremental aspects of using the algorithm; therefore, he eventually chose “dynamic programming” to effectively summarize the intent of the steps he was creating (~~Dreyfus~~).		As mentioned, Richard Bellman – a well renowned Stanford professor that was contracting for a non-profit research institution at the time – founded monumental principles on dynamic programming beginning in the 1950s when he started publishing formal work on the topic. In his first publishing, Bellman was forced to strategically name the new computational method due to political condemnation. To avoid using words like “research” and “mathematical,” Bellman sought to emphasize the time-varying and incremental aspects of using the algorithm; therefore, he eventually chose “dynamic programming” to effectively summarize the intent of the steps he was creating <ref>Dreyfus, S. (2002, February). Richard Bellman on the Birth of Dynamic Programming, pp. 48-51.</ref>.

	After learning more about the principles and mechanics of dynamic programming, it is intended to aid in decision-making challenges that have the specific circumstantial opportunities for its use. In particular, anything similar to the applications that are discussed later are concrete examples of where and how dynamic programming can be implemented. As these examples will show, the main objectives are to show the ease of dynamic programming in practice, exactly how this takes place, and what some of the drawbacks and limitations might be. Having this tool widely available, easily deployable, and readily adaptable for any fitting situation has changed the way that optimization can occur for the better.		After learning more about the principles and mechanics of dynamic programming, it is intended to aid in decision-making challenges that have the specific circumstantial opportunities for its use. In particular, anything similar to the applications that are discussed later are concrete examples of where and how dynamic programming can be implemented. As these examples will show, the main objectives are to show the ease of dynamic programming in practice, exactly how this takes place, and what some of the drawbacks and limitations might be. Having this tool widely available, easily deployable, and readily adaptable for any fitting situation has changed the way that optimization can occur for the better.
Line 12:		Line 12:
	=Algorithm Discussion=		=Algorithm Discussion=

	When tackling a dynamic programming problem, there are generally ~~seven~~ key steps to follow. The first and most crucial step is determining whether dynamic programming is the right approach. A key indicator of this is whether the problem can be broken down into smaller, overlapping subproblems. Problems that involve minimizing or maximizing a quantity, or those that require counting possible arrangements, are often strong candidates for dynamic programming solutions.		When tackling a dynamic programming problem, there are generally a number of key steps to follow. The first and most crucial step is determining whether dynamic programming is the right approach. A key indicator of this is whether the problem can be broken down into smaller, overlapping subproblems. Problems that involve minimizing or maximizing a quantity, or those that require counting possible arrangements, are often strong candidates for dynamic programming solutions.<ref name=":0">Benjaminson, E. (2023, January). A Framework for Solving Dynamic Programming Problems. Github.io. sassafras13.github.io/SolvingDPProblems/. </ref>

	Once you’ve identified that dynamic programming is applicable, the next step is to identify the variables involved, particularly those that change as the subproblems are solved. These changing variables are critical to breaking the problem down into manageable pieces. To identify the key variables, it can be helpful to list out a few examples of subproblems and compare the parameters in each case. By analyzing which parameters vary between subproblems, you can determine the number of subproblems that need to be solved, which will guide the design of the solution.		Once you’ve identified that dynamic programming is applicable, the next step is to identify the variables involved, particularly those that change as the subproblems are solved. These changing variables are critical to breaking the problem down into manageable pieces. To identify the key variables, it can be helpful to list out a few examples of subproblems and compare the parameters in each case. By analyzing which parameters vary between subproblems, you can determine the number of subproblems that need to be solved, which will guide the design of the solution.

	The third step is to define the recurrence relation, which expresses how the solution to a larger subproblem can be constructed from solutions to smaller subproblems. The recurrence relation serves as the core of the dynamic programming approach, describing how to combine the results of smaller subproblems to build up the final solution. This relation is crucial because it provides the blueprint for how an optimal solution can be derived from previously computed values. It must be carefully defined to ensure that the solution builds progressively and efficiently. Once the recurrence relation is established, the next step is to identify the base cases. Base cases often represent the simplest, smallest possible inputs for which the solution is trivial or already known. For example, in a problem like Fibonacci number calculation, the base cases are typically the first two numbers of the sequence. Base cases are essential because they serve as the foundation for building up solutions to more complex subproblems. They also act as stopping conditions for the recursion or termination conditions for the iterative approach, ensuring that the algorithm does not run indefinitely.		The third step is to define the recurrence relation, which expresses how the solution to a larger subproblem can be constructed from solutions to smaller subproblems. The recurrence relation serves as the core of the dynamic programming approach, describing how to combine the results of smaller subproblems to build up the final solution.<ref>Luu, H. (2020, November). Dissecting Dynamic Programming – Top down & Bottom Up. Medium. hien-luu.medium.com/dissecting-dynamic-programming-top-down-bottom-up-3d3a1d62fbd7. </ref> This relation is crucial because it provides the blueprint for how an optimal solution can be derived from previously computed values. It must be carefully defined to ensure that the solution builds progressively and efficiently. Once the recurrence relation is established, the next step is to identify the base cases. Base cases often represent the simplest, smallest possible inputs for which the solution is trivial or already known.<ref name=":0" /> For example, in a problem like Fibonacci number calculation, the base cases are typically the first two numbers of the sequence. Base cases are essential because they serve as the foundation for building up solutions to more complex subproblems. They also act as stopping conditions for the recursion or termination conditions for the iterative approach, ensuring that the algorithm does not run indefinitely.

	The next decision is whether to implement a recursive or an iterative solution, which corresponds to the choice between a top-down (memoization) approach and a bottom-up (tabulation) approach. In a top-down approach, recursion is used to break the problem into smaller subproblems, with results stored in a cache (or memoization table) to avoid redundant calculations. This approach is typically easier to conceptualize and implement but can lead to stack overflow issues for deep recursions in some languages. In contrast, the bottom-up approach builds the solution iteratively, solving smaller subproblems first and progressively solving larger ones. This method tends to be more efficient in terms of space because it does not require the overhead of recursion but might be harder to understand initially. Both methods ultimately achieve the same goal, and the choice often depends on the specific problem and the programmer's preference.		The next decision is whether to implement a recursive or an iterative solution, which corresponds to the choice between a top-down (memoization) approach and a bottom-up (tabulation) approach. In a top-down approach, recursion is used to break the problem into smaller subproblems, with results stored in a cache (or memoization table) to avoid redundant calculations.<ref name=":0" /> This approach is typically easier to conceptualize and implement but can lead to stack overflow issues for deep recursions in some languages. In contrast, the bottom-up approach builds the solution iteratively, solving smaller subproblems first and progressively solving larger ones. This method tends to be more efficient in terms of space because it does not require the overhead of recursion but might be harder to understand initially. Both methods ultimately achieve the same goal, and the choice often depends on the specific problem and the programmer's preference.

	The next step is to incorporate memoization (if using the top-down approach) or tabulation (for the bottom-up approach). Memoization improves performance by storing the results of expensive function calls so that they don’t need to be recomputed. When a subproblem is solved for the first time, its result is stored in a table or dictionary. If the same subproblem needs to be solved again, the stored result is returned instead of recalculating it. This prevents redundant work, leading to significant time savings, particularly for problems with overlapping subproblems.		The next step is to incorporate memoization (if using the top-down approach) or tabulation (for the bottom-up approach). Memoization improves performance by storing the results of expensive function calls so that they don’t need to be recomputed.<ref name=":0" /> When a subproblem is solved for the first time, its result is stored in a table or dictionary. If the same subproblem needs to be solved again, the stored result is returned instead of recalculating it. This prevents redundant work, leading to significant time savings, particularly for problems with overlapping subproblems.

	Finally, once you have implemented memoization (or tabulation), the last step is to analyze the time complexity of your solution. In dynamic programming, the time complexity is determined by two factors: the number of unique subproblems that must be solved, and the time required to solve each subproblem. The number of unique subproblems is determined by the number of distinct states defined by the changing parameters, while the time complexity per subproblem typically depends on the amount of work required to compute each solution. By carefully counting the number of subproblems and the cost of solving each one, you can estimate the overall time complexity of your dynamic programming solution. Often, dynamic programming solutions reduce the time complexity from exponential to polynomial time, making otherwise intractable problems solvable.		Finally, once you have implemented memoization (or tabulation), the last step is to analyze the time complexity of your solution. In dynamic programming, the time complexity is determined by two factors: the number of unique subproblems that must be solved, and the time required to solve each subproblem. The number of unique subproblems is determined by the number of distinct states defined by the changing parameters, while the time complexity per subproblem typically depends on the amount of work required to compute each solution. By carefully counting the number of subproblems and the cost of solving each one, you can estimate the overall time complexity of your dynamic programming solution. Often, dynamic programming solutions reduce the time complexity from exponential to polynomial time, making otherwise intractable problems solvable.

Fall2024 Team 22 Wiki at 17:57, 15 December 2024

2024-12-15T17:57:49Z

← Older revision		Revision as of 13:57, 15 December 2024
Line 232:		Line 232:
	Let’s start with our first state, s=11, where there are 11 lbs of berries left to add to the fruitcake.		Let’s start with our first state, s=11, where there are 11 lbs of berries left to add to the fruitcake.

	<math> ~~U_2~~(11) = \{0, 1, \dots, \min \{a[2], \lfloor ~~11w~~[2] \rfloor \}\}		<math>U_1(11) = \{0, 1, \dots, \min \{a[2], \left\lfloor \frac{11}{w[2]} \right\rfloor\}\}
	</math>


			</math>

	<math>U_2(11) = \{0, 1, 2, 3\} \quad \text{since } a[2] = 4 \text{ and } \left\lfloor \frac{11}{3} \right\rfloor = 3.		<math>U_2(11) = \{0, 1, 2, 3\} \quad \text{since } a[2] = 4 \text{ and } \left\lfloor \frac{11}{3} \right\rfloor = 3.
Line 456:		Line 459:
	\|-		\|-
	\|0		\|0
	\|= 0 + f2*(11) = 0 + 4 = 4		\|= 0 +<math>f_2^{*}(11)

			</math> = 0 + 4 = 4
	\|-		\|-
	\|1		\|1
	\|= 2 + f2*(9) = 2 + 4 = 6		\|= 2 + <math>f_2^{*}(9)

			</math> = 2 + 4 = 6
	\|-		\|-
	\|2		\|2
	\|= 3 + f2*(7) = 3 + 2 = 5		\|= 3 + <math>f_2^{*}(7)

			</math> = 3 + 2 = 5
	\|-		\|-
	\|3		\|3
	\|= 5 + f2*(5) = 5 + 1 = 6		\|= 5 + <math>f_2^{*}(5)

			</math> = 5 + 1 = 6
	\|-		\|-
	\|'''4'''		\|'''4'''
	\|'''= 7 + f2*(3) = 6 + 1 = 8'''		\|'''= 7 + <math>f_2^{*}(3)

			</math> = 6 + 1 = 8'''
	\|}		\|}

Fall2024 Team 22 Wiki: /* Example 2: Layered Graphs */

2024-12-15T17:16:32Z

Example 2: Layered Graphs

← Older revision		Revision as of 13:16, 15 December 2024
Line 26:		Line 26:
	=Numerical Examples=		=Numerical Examples=

	=== '''''Example 1: ~~A Smaller Size~~ Knapsack Problem''''' ===		=== '''''Example 1: Knapsack Problem''''' ===
	''The Smiths are trying to replicate a delicious Christmas fruitcake recipe, and the recipe calls for berries with a total of up to 11 lbs of berries packed into the fruitcake. The Smiths purchased 4 boxes of strawberries and 4 boxes of blueberries during their Christmas grocery shopping trip last weekend but are unsure of how many boxes of strawberries and blueberries to include in their fruitcake. Each box of strawberries weighs 2 lbs and each box of blueberries weighs 3 lbs. To make the choice easier, they spent all day researching how different amounts of strawberries and blueberries impact the taste of the fruitcake and made a benefit table listing the value each box of berries adds to the overall taste of the fruitcake. The benefit table is shown below in Table 1. Please use Dynamic Programming to help the Smiths choose the optimal number of boxes of strawberries and blueberries to include in their delicious Christmas fruitcake this year!''		''The Smiths are trying to replicate a delicious Christmas fruitcake recipe, and the recipe calls for berries with a total of up to 11 lbs of berries packed into the fruitcake. The Smiths purchased 4 boxes of strawberries and 4 boxes of blueberries during their Christmas grocery shopping trip last weekend but are unsure of how many boxes of strawberries and blueberries to include in their fruitcake. Each box of strawberries weighs 2 lbs and each box of blueberries weighs 3 lbs. To make the choice easier, they spent all day researching how different amounts of strawberries and blueberries impact the taste of the fruitcake and made a benefit table listing the value each box of berries adds to the overall taste of the fruitcake. The benefit table is shown below in Table 1. Please use Dynamic Programming to help the Smiths choose the optimal number of boxes of strawberries and blueberries to include in their delicious Christmas fruitcake this year!''

Fall2024 Team 22 Wiki: /* Numerical Examples */

2024-12-15T17:15:50Z

Numerical Examples

← Older revision		Revision as of 13:15, 15 December 2024
Line 25:		Line 25:

	=Numerical Examples=		=Numerical Examples=
	~~'''''Example 1: A Smaller Size Knapsack Problem'''''~~

			=== '''''Example 1: A Smaller Size Knapsack Problem''''' ===
	''The Smiths are trying to replicate a delicious Christmas fruitcake recipe, and the recipe calls for berries with a total of up to 11 lbs of berries packed into the fruitcake. The Smiths purchased 4 boxes of strawberries and 4 boxes of blueberries during their Christmas grocery shopping trip last weekend but are unsure of how many boxes of strawberries and blueberries to include in their fruitcake. Each box of strawberries weighs 2 lbs and each box of blueberries weighs 3 lbs. To make the choice easier, they spent all day researching how different amounts of strawberries and blueberries impact the taste of the fruitcake and made a benefit table listing the value each box of berries adds to the overall taste of the fruitcake. The benefit table is shown below in Table 1. Please use Dynamic Programming to help the Smiths choose the optimal number of boxes of strawberries and blueberries to include in their delicious Christmas fruitcake this year!''		''The Smiths are trying to replicate a delicious Christmas fruitcake recipe, and the recipe calls for berries with a total of up to 11 lbs of berries packed into the fruitcake. The Smiths purchased 4 boxes of strawberries and 4 boxes of blueberries during their Christmas grocery shopping trip last weekend but are unsure of how many boxes of strawberries and blueberries to include in their fruitcake. Each box of strawberries weighs 2 lbs and each box of blueberries weighs 3 lbs. To make the choice easier, they spent all day researching how different amounts of strawberries and blueberries impact the taste of the fruitcake and made a benefit table listing the value each box of berries adds to the overall taste of the fruitcake. The benefit table is shown below in Table 1. Please use Dynamic Programming to help the Smiths choose the optimal number of boxes of strawberries and blueberries to include in their delicious Christmas fruitcake this year!''

Line 615:		Line 615:
	'''Final Answer: The Smiths should add 4 boxes of strawberries and 1 box of blueberries to their fruitcake.'''		'''Final Answer: The Smiths should add 4 boxes of strawberries and 1 box of blueberries to their fruitcake.'''

			=== '''''Example 2: Layered Graphs''''' ===
	'''''Example 2: Layered Graphs'''''

	''Find the shortest path in this layered graph using the concepts of dynamic programming.''		''Find the shortest path in this layered graph using the concepts of dynamic programming.''
	[[File:Layered Graph for dynamic programming.jpg\|center\|thumb\|405x405px\|Layered graph to find shortest path using dynamic programming.]]		[[File:Layered Graph for dynamic programming.jpg\|center\|thumb\|405x405px\|Layered graph to find shortest path using dynamic programming.]]

Fall2024 Team 22 Wiki at 17:14, 15 December 2024

2024-12-15T17:14:07Z

← Older revision		Revision as of 13:14, 15 December 2024
Line 97:		Line 97:
	<math>		<math>
	f_n^*(s)		f_n^*(s)
	</math> is the value of the maximum benefit possible with items of type n (or greater) while fitting into the remaining capacity s.		</math> is the value of the maximum benefit possible with items of type n (or greater) while fitting into the remaining capacity s.

	'''Step 5: What are the boundary conditions?'''		'''Step 5: What are the boundary conditions?'''

Fall2024 Team 22 Wiki at 17:12, 15 December 2024

2024-12-15T17:12:33Z

← Older revision		Revision as of 13:12, 15 December 2024
Line 97:		Line 97:
	<math>		<math>
	f_n^*(s)		f_n^*(s)
	</math> is the value of the maximum benefit possible with items of type n (or greater) while fitting into the remaining capacity s.		</math> is the value of the maximum benefit possible with items of type n (or greater) while fitting into the remaining capacity s.

	'''Step 5: What are the boundary conditions?'''		'''Step 5: What are the boundary conditions?'''
Line 658:		Line 658:

	Because of how many variables are present in vehicle dynamics, it is certainly a prime application for dynamic programming. Specifically, there are unique objective functions for all types of vehicles due to their range in purpose. Lukic and Wang’s study on hybrid engine performance simulated a vehicle's configuration and how a set of parameters affected fuel consumption. For example, the effect of vehicle mass, planetary gear ratios, frontal surface area, maximum battery capacity, and few others were all evaluated to maximize the fuel economy (Wang and Lukic).		Because of how many variables are present in vehicle dynamics, it is certainly a prime application for dynamic programming. Specifically, there are unique objective functions for all types of vehicles due to their range in purpose. Lukic and Wang’s study on hybrid engine performance simulated a vehicle's configuration and how a set of parameters affected fuel consumption. For example, the effect of vehicle mass, planetary gear ratios, frontal surface area, maximum battery capacity, and few others were all evaluated to maximize the fuel economy (Wang and Lukic).
			[[File:Wiki - Dynamic Programming.docx (1).jpg\|center\|thumb\|468x468px\|A results table from Lukic and Wang’s study that shows the optimal values of 0.9 and 0.5 for most optimal for best fuel economy.]]

			=Conclusion=
			In conclusion, dynamic programming has changed the way that optimization problems can be solved.. Solving a dynamic programming problem begins with a critical assessment of whether dynamic programming is the right approach. This is determined by analyzing the problem's structure—specifically, whether it can be broken down into smaller, overlapping subproblems. If the problem exhibits these characteristics, it suggests that dynamic programming can provide an efficient solution.

			DP is a valuable optimization method because of its ability to split and store subproblems to reach a global optimal value. Even further, it has the capability of working with all types of data whether it be complex numerical models or descriptions as strings of text. As seen with the examples in previous sections, a multitude of sectors benefit from the strengths and flexibility of DP. Considering dynamic programming has been developed into the largely inclusive tool that it is now, there are not many paths for its future directions. The algorithm has been and is continuously thoroughly examined and incorporated into viable solution spaces.
	~~=Conclusion=~~
	~~The eight-step procedure~~ is ~~an approach used in dynamic programming~~ to ~~transform~~ a ~~problem into simpler problems to yield an~~ optimal ~~solution~~. ~~The recursive nature~~ of the ~~procedure allows for~~ the ~~optimization problems to be solved using computational models~~ that ~~reduce time~~ and ~~effort~~ and ~~can be used in many applications across many industries~~.

	=References=		=References=
	<references />		<references />

Fall2024 Team 22 Wiki at 17:08, 15 December 2024

2024-12-15T17:08:41Z

Show changes

Fall2024 Team 22 Wiki: /* Numerical Example */

2024-12-15T17:00:09Z

Numerical Example

← Older revision		Revision as of 13:00, 15 December 2024
Line 44:		Line 44:
	This is the final step for solving a problem using the eight step procedure. <br />		This is the final step for solving a problem using the eight step procedure. <br />

	=Numerical ~~Example~~=		=Numerical Examples=
	'''''Example 1: A Smaller Size Knapsack Problem'''''		'''''Example 1: A Smaller Size Knapsack Problem'''''

Line 636:		Line 636:


	'''Example 2: Layered Graphs'''		'''''Example 2: Layered Graphs'''''

	Find the shortest path in this layered graph using the concepts of dynamic programming.		''Find the shortest path in this layered graph using the concepts of dynamic programming.''
	[[File:Layered Graph for dynamic programming.jpg\|center\|thumb\|405x405px\|Layered graph to find shortest path using dynamic programming.]]		[[File:Layered Graph for dynamic programming.jpg\|center\|thumb\|405x405px\|Layered graph to find shortest path using dynamic programming.]]
	We can partition the nodes into layers where the first layer is s, the second layer is A, B, and C, the third layer is D and E, the fourth layer is F and G, and the fifth layer is t. We will make a decision of the path to take at each layer, and each decision will correspond to a stage of the dynamic programming problem.		We can partition the nodes into layers where the first layer is s, the second layer is A, B, and C, the third layer is D and E, the fourth layer is F and G, and the fifth layer is t. We will make a decision of the path to take at each layer, and each decision will correspond to a stage of the dynamic programming problem.

Fall2024 Team 22 Wiki at 16:59, 15 December 2024

2024-12-15T16:59:24Z

Show changes