Calculator overview
Inputs and outputs
This summary comes from the calculator's published input and output contract.
Inputs
- Reward bars (row u is the reward of each project with u units; a blank cell pays nothing)
-
When omitted Blank
Default 12 rows
About this input
The reward bars: row u is the reward of each project with u units, a whole number from 0 to 200 points; a blank cell pays nothing, and no units always pay 0. Every cell is checked, also for projects above the number in use. Drawn as one bar chart per project on the canvas.
Column Range or allowed values Project 1 0 to 200 Project 2 0 to 200 Project 3 0 to 200 Project 4 0 to 200 Project 5 0 to 200 - Your units for project 1 (required)
-
Default 3 Range 0 to 12
About this input
Your plan: the units you give project 1, a whole number from 0 to 12 (the marker under its chart). Ignored above the number of projects.
- Cap of project 5 (required)
-
Default 12 Range 0 to 12
About this input
The cap of project 5: the most units it may take, a whole number from 0 to 12. Ignored above the number of projects.
- Number of projects (required)
-
Default 3 Range 2 to 5
About this input
The number of projects sharing the budget, a whole number from 2 to 5. Set by the chip on the canvas; the bars, caps and units of projects above it are kept but ignored.
- Your units for project 4 (required)
-
Default 0 Range 0 to 12
About this input
Your plan: the units you give project 4, a whole number from 0 to 12 (the marker under its chart). Ignored above the number of projects.
- Your units for project 5 (required)
-
Default 0 Range 0 to 12
About this input
Your plan: the units you give project 5, a whole number from 0 to 12 (the marker under its chart). Ignored above the number of projects.
- Your units for project 2 (required)
-
Default 3 Range 0 to 12
About this input
Your plan: the units you give project 2, a whole number from 0 to 12 (the marker under its chart). Ignored above the number of projects.
- Your units for project 3 (required)
-
Default 2 Range 0 to 12
About this input
Your plan: the units you give project 3, a whole number from 0 to 12 (the marker under its chart). Ignored above the number of projects.
- Your prediction of the best total (challenge 1)
-
When omitted Blank
Default Not set Range 0 to 1000
About this input
Challenge 1: your prediction of the best total, a whole number from 0 to 1000. Blank until you predict; the best plan and its total stay hidden until then. Not used outside challenge 1.
- Your prediction of one more unit (challenge 4)
-
When omitted Blank
Default Not set Range 0 to 200
About this input
Challenge 4: your prediction of what one more unit adds to the best total, a whole number from 0 to 200. Blank until you predict; the results that give it away stay hidden until then. Not used outside challenge 4.
- Budget (units) (required)
-
Default 8 Range 1 to 12
About this input
The budget: the whole units to share, from 1 to 12. Units may be left unspent.
- Challenge (required)
-
Default 0 Range 0 to 5
About this input
Selects a challenge: 0 for none, 1 to 5 for a predefined challenge, which loads its own projects, budget, caps and bars and leaves only some inputs to you.
- Cap of project 3 (required)
-
Default 12 Range 0 to 12
About this input
The cap of project 3: the most units it may take, a whole number from 0 to 12. Ignored above the number of projects.
- Cap of project 4 (required)
-
Default 12 Range 0 to 12
About this input
The cap of project 4: the most units it may take, a whole number from 0 to 12. Ignored above the number of projects.
- Cap of project 1 (required)
-
Default 12 Range 0 to 12
About this input
The cap of project 1: the most units it may take, a whole number from 0 to 12. Ignored above the number of projects.
- Cap of project 2 (required)
-
Default 12 Range 0 to 12
About this input
The cap of project 2: the most units it may take, a whole number from 0 to 12. Ignored above the number of projects.
Outputs
- Best total
-
No unit declared
About this output
The best total: the largest total reward of any plan that respects the caps and the budget, found by backward induction. Blank when the inputs are not valid and while challenge 1 or 4 awaits a prediction.
- Best plans
-
No unit declared
About this output
One best plan, or several plans tie for the best total (the lattice shows the one with the fewest units for earlier projects). Blank when the inputs are not valid and while challenge 2 or 3 is unsolved.
- The plans: each project's cap, the best plan, greedy's plan and your plan with their rewards, and whether its returns never rise
-
No unit declared
About this output
One row per project (rows above the number of projects blank): the cap, the best plan's units and reward, greedy's units and reward, your units and reward (blank when your plan does not fit), and 1 when its returns never rise within the budget. The best-plan and greedy columns follow the challenge withholding.
- Number of best plans
-
No unit declared
About this output
The number of different plans that reach the best total (plans differing only in unspent units count separately). Blank when the inputs are not valid and while challenge 2 or 3 is unsolved.
- Model version
-
No unit declared
About this output
The model version.
- Formula module versions
-
No unit declared
About this output
The formula modules the model is built from, with their versions.
- Value of one more unit
-
No unit declared
About this output
The value of one more unit: how much the best total would rise with one more unit of budget. Blank at a budget of 12, when the inputs are not valid and while challenge 1 or 4 awaits a prediction.
- Backward induction: the best total from project k to the last project with b units, the best units for project k, and the value of the last unit
-
No unit declared
About this output
Backward induction for every budget b = 0 to 12: the best total from project k to the last project, the best units for project k (blank above the number of projects), and the value of the last unit. Blank while a challenge hides the best plan.
- Your plan
-
No unit declared
About this output
Whether your plan fits: the units used of the budget, the project above its cap, or how far the plan is over the budget. Blank when the inputs are not valid.
- Your total
-
No unit declared
About this output
The total reward of your plan. Blank when the inputs are not valid or when your plan does not fit its caps or the budget.
- The shape library: four reward shapes the page can copy into a project's bars
-
No unit declared
About this output
The shape library: the rewards of the Steady, Diminishing, S-curve and Threshold shapes for 1 to 12 units, which the page can copy into a project's bars. Shown in every state.
- The stage lattice: one row per node (project k, units left b), its best decision, the units left after it, its tied choices and best plans from here, and the fill and path frames of the player
-
No unit declared
About this output
The stage lattice: one row per node (project k, units left b = 0 to 12; rows above the number of projects blank) with the best units, the units left after them, the tied choices, the best plans from here, the fill frame (budgets up to B, filled from the last project back) and the path frame of the best plan. The decision and path columns are blank while a challenge hides the best plan, the tie columns while challenge 2 or 3 is unsolved.
- Projects used
-
No unit declared
About this output
The number of projects used (the challenge's when a challenge is selected). Blank when the inputs are not valid.
- The rewards used (in a challenge, the locked bars)
-
No unit declared
About this output
The rewards used for 1 to 12 units (in a challenge, the locked bars), blank above the number of projects.
- Challenge: the value scored
-
No unit declared
About this output
The value the selected challenge scores: the best total (challenge 1), your total (2 and 3), the value of one more unit (4) or the greedy shortfall (5); blank with none, when not valid, while a prediction is awaited, or when your plan does not fit (2 and 3).
- Challenge score
-
No unit declared
About this output
The challenge score: 100 when met, else 0.
- Challenge result
-
No unit declared
About this output
No challenge selected, MET or NOT MET.
- Challenge goal
-
No unit declared
About this output
The goal of the selected challenge (blank with none).
- Possible plans
-
No unit declared
About this output
The number of possible plans within the caps and the budget (6,188 at 5 projects and 12 units with no cap), which a search of every plan would have to check. Blank when the inputs are not valid.
- Budget used
-
No unit declared
About this output
The budget used (the challenge's when a challenge is selected). Blank when the inputs are not valid.
- Challenge feedback
-
No unit declared
About this output
Feedback on the selected challenge: the prediction prompt, the met text or the not-met hint (blank with none).
- Greedy, step by step: the project chosen, its gain, the running total and every project's units after the step
-
No unit declared
About this output
Greedy step by step for steps 1 to B: the project chosen and its gain (blank once greedy stops), the running total and every project's units after the step. Blank while challenge 1 or 4 awaits a prediction and while challenge 3 is unsolved.
- Greedy total
-
No unit declared
About this output
The total reached by the greedy rule, which gives each next unit to the biggest immediate gain and stops when no unit gains anything. Blank when the inputs are not valid, while challenge 1 or 4 awaits a prediction and while challenge 3 is unsolved.
- Model Status
-
No unit declared
About this output
NOT VALID with the reason when an input cannot be used; otherwise OK. Tied best plans, greedy missing the best plan, unspent units and a plan of yours that does not fit are results, not warnings.
- Greedy shortfall
-
No unit declared
About this output
The best total minus the greedy total (at least 0). Blank when the inputs are not valid, while challenge 1 or 4 awaits a prediction and while challenge 3 is unsolved.
- Decisions the recursion checks
-
No unit declared
About this output
The number of decisions backward induction checks at your projects, budget and caps (455 at 5 projects and 12 units with no cap). Blank when the inputs are not valid.
- Gap to the best total
-
No unit declared
About this output
The best total minus your total (at least 0). Blank when the inputs are not valid, when your plan does not fit, and while challenge 1 or 4 awaits a prediction.
- Is greedy guaranteed?
-
No unit declared
About this output
Whether greedy is sure to find a best plan: guaranteed when no project's extra reward per unit rises within the budget, otherwise the lowest project whose returns rise. Blank when the inputs are not valid.
LogicCommons is in beta. If a result, label, or reference looks wrong, tell us here; we read every message.
Methodology
Purpose and model boundary
This lab shares a budget of up to 12 whole units among 2 to 5 projects. Each project pays a reward, in whole points, for each number of units it receives, and may have a cap on the units it can take. Units may be left unspent. The model finds the best plan exactly by backward induction (dynamic programming) and shows the recursion as a lattice of stages and budgets. It counts exactly how many plans tie for the best total and how many plans exist at all, plays the greedy rule step by step with its shortfall, states when greedy is guaranteed to find a best plan, gives the value of one more unit, and scores your own plan against the best. Five challenges are scored by the model.
It is a lab for learning dynamic programming and why a greedy rule can fail: when a project pays little for its first units and a lot later, a rule that judges one unit at a time never starts it, while backward induction sees the whole curve. It is not a planning or budgeting method for real projects: there is one resource, rewards are fixed tables of whole points, projects do not interact, and nothing is uncertain.
The model is the calculation authority. The page sends the values you set to the model and draws only what it returns: the reward bar charts with their caps and the best plan's bars outlined, your markers and greedy's markers, the stage lattice with its fill and best path, and at the Advanced level the value table as a heat map and the value of the last unit. The page computes no total, plan, count or gain itself.
Inputs and units
Units are whole units of the shared resource; rewards are whole points.
| Input | Meaning and unit |
|---|---|
| Number of projects | A whole number from 2 to 5 (default 3). Projects above it keep their bars, caps and units, but are ignored. |
| Budget (units) | A whole number from 1 to 12 (default 8): the units to share. Units may be left unspent. |
| Reward bars | For each project, the reward with 1 to 12 units: a whole number from 0 to 200 points, or blank, which pays nothing. No units always pay 0. Every bar is checked, also for projects above the number in use. The defaults are, in order, the Diminishing, S-curve, Steady, Threshold and Diminishing shapes (below). |
| Cap of project 1 to 5 | A whole number from 0 to 12 each (default 12): the most units that project may take. |
| Your units for project 1 to 5 | A whole number from 0 to 12 each (defaults 3, 3, 2, 0, 0): your plan. |
| Challenge | 0 for none, or 1 to 5. |
| Your prediction of the best total | Blank, or a whole number from 0 to 1000: your answer for challenge 1. |
| Your prediction of one more unit | Blank, or a whole number from 0 to 200: your answer for challenge 4. |
The shape library offers four reward shapes the page can copy into a project's bars, which stay editable: Steady (8 points a unit), Diminishing (100·(1 - 0.8^u) rounded to whole points: 20, 36, 49, ... 93), S-curve (slow, then steep, then level: 2, 5, 10, 20, 40, 60, ... 96) and Threshold (nothing until 4 units, then 60 and 4 more a unit).
Where each input is set:
- On the canvas only: the number of projects, with a chip; the reward bars, dragged on each project's bar chart in whole points (an exact value can be typed in the bar's popover, and the shape menu copies a shape in); and your plan, with a marker under each project's chart, kept within its cap and the budget left. None of these is in the input panel.
- In the input panel: the budget; the caps, in the Caps table (rows above the number of projects are hidden); and the challenge picker. The best-total prediction box appears only in challenge 1, and the one-more-unit prediction box only in challenge 4.
Governing relationships
The problem. With K projects, a budget of B units, r_k(x) the reward of project k with x units (r_k(0) = 0, a blank bar read as 0) and c_k its cap, choose whole units x_1 to x_K with each x_k from 0 to c_k and a total of at most B, to make the total reward r_1(x_1) + ... + r_K(x_K) as large as possible.
Backward induction (Bellman's principle of optimality). Let V_k(b) be the best total from projects k to K with b units left. Working from the last project back to the first, for every b from 0 to 12:
V_k(b) = max over x = 0 to min(b, c_k) of [ r_k(x) + V_(k+1)(b - x) ], with V_(K+1)(b) = 0.
The best total is V_1(B). The best decision X_k(b) is the smallest x that reaches the maximum; this tie rule makes the plan shown the one with the fewest units for earlier projects. Following the decisions forward from b = B gives the best plan: x_1 = X_1(B), then x_2 = X_2(B - x_1), and so on. Projects above K get a cap of 0, so their stages change nothing.
Counting. The number of tied choices at a node is the number of decisions x that reach V_k(b). The number of best plans from a node, N_k(b), adds up the best plans from the next node over every tied choice, with 1 at the end. The number of possible plans counts every plan within the caps and the budget the same way, ignoring the rewards; with no binding cap it is the binomial coefficient C(B + K, K), for example 6,188 at 5 projects and 12 units. Plans that differ only in unspent units count as different plans. The decisions the recursion checks are the sum over the projects of the allowed (b, x) pairs up to the budget: 455 at 5 projects and 12 units with no cap. The comparison shows the size of the search the recursion avoids.
The greedy rule. Starting from no units, at each step greedy gives one unit to the project with the largest immediate gain r_k(a_k + 1) - r_k(a_k), among projects still below their cap, with ties going to the lowest project number. It stops when the budget is spent or when no unit would gain anything, so it never takes a unit that adds 0 or less. The greedy shortfall is the best total minus greedy's total, never below 0.
When greedy is guaranteed. A project's returns rise where its second difference r_k(u + 1) - 2·r_k(u) + r_k(u - 1) is positive, that is, where the extra reward of one more unit grows. If no project in use has rising returns at any u + 1 it can reach (within its cap and the budget), greedy finds a best plan: the classic marginal-analysis result for separable concave rewards with a shared budget. Otherwise greedy is not guaranteed and can miss the best plan, although it may still find it.
The value of one more unit. V_1(b) - V_1(b - 1) for each b from 1 to 12, and at your budget V_1(B + 1) - V_1(B) (blank at a budget of 12). It is never negative, because units may be left unspent. With diminishing returns it never rises; with an S-shaped or threshold project it can rise, because one more unit can switch the best plan to a different project.
Your plan. Your plan fits when no project in use has more units than its cap and the total is at most the budget. Then your total is the sum of the rewards of your units, and the gap is the best total minus yours.
Calculation sequence
- Check the inputs in the order of the list under Errors and warnings.
- In a challenge, replace the number of projects, the budget, the caps and the locked reward bars with the challenge's own.
- Run backward induction for the five stages and every budget from 0 to 12: the values, the best decisions, the tied choices and the counts of best and possible plans.
- Follow the decisions forward from the budget to get the best plan.
- Play greedy step by step; test every project's returns for a rise; compute the value of each unit.
- Score your plan, set the status and, in a challenge, score it.
Outputs and interpretation
- Best total and best plans (one best plan, or several tied, with the lattice showing the one with the fewest units for earlier projects), and the number of best plans.
- Your total, gap to the best total and your plan: whether it fits, the units used of the budget, the project above its cap, or how far the plan is over the budget.
- Greedy total, greedy shortfall and is greedy guaranteed? (guaranteed, or not guaranteed with the lowest project whose returns rise).
- Value of one more unit.
- Decisions the recursion checks and possible plans.
- Settings used: the projects and budget in effect (a challenge may fix them), and the model version.
- Tables: the stage lattice (one row per project and units left: the best units, the units left after, the tied choices, the best plans from here, and the fill and path frames of the player); the value table (for every budget, the best total from each project on, the best units for each project and the value of the last unit); the rewards used; greedy step by step (the project chosen, its gain, the running total and every project's units); the plan table (each project's cap, the best plan's, greedy's and your units and rewards, and whether its returns never rise); and the shape library.
Reading the canvas: each project's bar chart shows its rewards with the cap as a line and the best plan's bar outlined; your marker sits under the axis and greedy's marker steps along during its playback. In the lattice, each column is a project and each row a number of units left; the player fills the nodes from the last project back, the order backward induction works in, then draws the best path from the full budget. Nodes above the budget are faint and never fill.
What to take from the lab: backward induction finds the best plan by solving every smaller budget for the later projects once, instead of trying every plan; greedy is safe only when no project's returns rise; a project that pays little until it has several units hides its value from any rule that looks one unit ahead; and the value of one more unit can jump when it makes a different plan best.
Challenges
Each challenge sets its own projects, budget, caps (12 in every challenge) and reward bars, and leaves only some inputs to you. The model scores each one MET (100) or NOT MET (0) and gives a hint while it is not met.
- Predict the best. Five medical teams can go to three countries; the bars show the extra years of life (in thousands) for each number of teams. Predict the best total, within 5, before the plan is shown. Met when your prediction is within 5 of the best total.
- Beat greedy by hand. Greedy, which always gives the next unit to the biggest immediate gain, reaches 168 here. Move your markers to a plan worth the best total, 192. Met when your plan fits and its total equals the best total.
- Another way to win. Several plans reach the best total, 92, with 7 units. Find one that gives project 1 more units than project 2. Met when your plan fits, its total equals the best total and project 1 has more units than project 2.
- What is one more unit worth? The budget is 5 units. Predict exactly how many points a sixth unit would add to the best total. Met when your prediction equals the value of one more unit.
- Set the greedy trap. Projects 1 and 3 have diminishing returns and are locked. Reshape only project 2's bars so the best plan beats greedy by at least 10 points. Met when the greedy shortfall is at least 10.
Held-back results:
- Challenges 1 and 4, until you predict: the best total, the gap, the best plan (value table, best units and path), greedy's results and the value of one more unit are blank. Once you enter a number, 0 included, everything appears and the challenge is scored.
- Challenge 2, while not met: the best plan and the tie counts are blank; the best total is stated in the goal, and greedy's results stay.
- Challenge 3, while not met: the best plan, the tie counts and greedy's results are blank, because greedy's own plan is a winning answer here.
- Challenge 5 holds nothing back: both totals are the feedback on your design.
The rewards, your own total and plan check, the lattice layout and fill order, and the counts of decisions and possible plans stay visible in every challenge.
Validation and status logic
The status reads the first match in the list under Errors and warnings, checked on the values you entered, inside a challenge too. For the reward bars it names the first bar that fails, project by project and then unit by unit; for the caps and your units, the lowest project that fails. A challenge number that is not a whole number from 0 to 5 counts as no challenge. There is no CHECK message: tied best plans, greedy missing the best plan, unspent units and a plan of yours that does not fit are results, not warnings.
Assumptions and limitations
- One shared budget of at most 12 whole units; at most 5 projects; each project's reward a table of whole points from 0 to 200 for 0 to 12 units; an optional cap per project; unspent units allowed.
- No fractional units, no second resource, no interaction between projects, no uncertainty or timing.
- The recursion is exact; every value is a whole number and no decision depends on rounding.
- The lattice and the plan table show one best plan, the one with the fewest units for earlier projects; the number of best plans says how many tie. Greedy breaks its own ties toward the lowest project number.
- The greedy guarantee is a sufficient condition: greedy can find a best plan without it.
- The recursion fills all 13 budgets for every project even when the budget is smaller, so the value table and the value of one more unit are defined at every budget.
Restrictions and non-computing states
Under NOT VALID every result and every table entry is blank, except the model version, the shape library, the challenge result (No challenge selected, or NOT MET with a challenge selected), a score of 0, and the goal and hint of a selected challenge.
A plan of yours that does not fit is not NOT VALID: your total and the gap are blank, the plan check says what is wrong, and every other result is shown. The value of one more unit is blank at a budget of 12. In challenges the results listed under Challenges are held back.
Errors and warnings
The status messages, first match wins (k is a project number and u a number of units):
- NOT VALID: the number of projects must be a whole number from 2 to 5
- NOT VALID: the budget must be a whole number of units from 1 to 12
- NOT VALID: the reward for u units in project k must be blank or a whole number from 0 to 200: the first reward bar that fails (written "1 unit" for u = 1).
- NOT VALID: the cap of project k must be a whole number from 0 to 12
- NOT VALID: your units for project k must be a whole number from 0 to 12
- NOT VALID: the challenge number must be a whole number from 0 to 5, and each prediction blank or a whole number (best total 0 to 1000, one more unit 0 to 200)
- OK
References
This laboratory is an educational model of the discrete resource allocation problem: whole units of one budget shared among projects whose rewards are given for each number of units. It is solved exactly by dynamic programming, using Bellman's principle of optimality to work backward from the last project through every smaller budget. Beside it runs the greedy rule of marginal analysis, which gives each next unit to the largest immediate gain and is guaranteed to be optimal when no project's returns rise. The exact counts of tied best plans and of all plans show how much search the recursion avoids.
Sources and further reading
- The principle of optimality and the functional equation of dynamic programming: R. Bellman, "On the theory of dynamic programming", Proceedings of the National Academy of Sciences of the USA 38(8), 1952, pages 716-719. doi:10.1073/pnas.38.8.716
- Dynamic programming as an algorithmic technique that reuses the solutions of subproblems: NIST, Dictionary of Algorithms and Data Structures, entry "dynamic programming". NIST
- The greedy algorithm, which takes the best immediate choice and may miss the optimum: P. E. Black, NIST, Dictionary of Algorithms and Data Structures, entry "greedy algorithm". NIST
- The principle of optimality applied to resource allocation, and greedy methods beside it: G. Kocur, Computer Algorithms in Systems Engineering (1.204), MIT OpenCourseWare, Spring 2010, lecture notes, lecture 13, Principle of optimality, resource allocation. MIT OpenCourseWare
- Marginal analysis and when it is optimal for separable concave allocation problems: B. Fox, "Discrete optimization via marginal analysis", Management Science 13(3), 1966, pages 210-216. doi:10.1287/mnsc.13.3.210
- Deterministic dynamic programming and the classic example of distributing medical teams to countries: F. S. Hillier and G. J. Lieberman, Introduction to Operations Research, McGraw-Hill, the chapter on dynamic programming.
Challenge 1 uses the numbers of the medical-teams example from Hillier and Lieberman, cited above as its source. No other table and no text from any of these publications is reproduced, and none of their authors or publishers has reviewed or endorses this laboratory.
This laboratory is for learning. Its results hold only within its stated ranges; real allocation decisions involve uncertain rewards, several resources and interactions between projects, which this lab leaves out.
Links were current at build time. If one moves, search the document's title rather than reporting a broken link as a defect.
Found a problem, or have an idea?
Tell us if a result looks wrong, a label is unclear, or something is missing. We read every message.