Greedy Subgoal Scheduling Under a Step Budget

mediumPROAgent Loop Control & PlanningAI AgentsAI Agents 1

Problem Statement

An agent must pick which subgoals to pursue within a fixed step budget to maximize total value. Each subgoal costs some steps and yields some value; pick the subset with the greatest value that fits.

Background

This is 0/1 knapsack: with budget steps and subgoals each {"steps": int, "value": int}, choose a subset whose total steps <= budget maximizing total value. Return the max achievable value.

Your Task

def schedule_subgoals(subgoals, budget):

Return the maximum total value (int).

Input Format

subgoals (list of dicts), budget (int).

Output Format

A single int.

Sample

print(schedule_subgoals([{"steps":2,"value":3},{"steps":3,"value":4},{"steps":4,"value":5}], 5))

Output:

Example

Input

print(schedule_subgoals([{"steps":2,"value":3},{"steps":3,"value":4},{"steps":4,"value":5}], 5))

Output

Reasoning

Initialize a value tracker for step budgets 0 through 5, starting with all zeros: $[0, 0, 0, 0, 0, 0]$ .
Process the first subgoal (cost 2, value 3): update the tracker so that any budget $\ge 2$ can hold this item. The tracker becomes $[0, 0, 3, 3, 3, 3]$ , meaning a budget of 2 or more yields a value of 3.
Process the second subgoal (cost 3, value 4): check if adding this item improves the value for budgets $\ge 3$ . For budget 5, combining the first subgoal (cost 2, value 3) with this one (cost 3, value 4) exceeds the budget, but for budget 5, we compare keeping the previous best (3) versus taking this item alone (4) or combining with a previous item that fits. Specifically, at budget 5, $dp[5-3] + 4 = dp[2] + 4 = 3 + 4 = 7$ , which is better than the current 3. The tracker updates to $[0, 0, 3, 4, 4, 7]$ .
Process the third subgoal (cost 4, value 5): check budgets $\ge 4$ . For budget 5, combining this with the first subgoal (cost 2, value 3) gives total cost 6, which exceeds the budget. Taking it alone gives value 5, which is less than the current best of 7. The tracker remains $[0, 0, 3, 4, 4, 7]$ .
The final output is 7

Constraints

0 <= budget <= 5000, non-negative int steps/values, len <= 200.
Classic 0/1 knapsack; each subgoal used at most once.
Return the max value.

Learn this in

Dynamic Programming AdvancedDSA Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primerPREVIEW

1. Background Knowledge

This problem is a classic instance of the 0/1 Knapsack Problem, a fundamental optimization challenge in computer science and operations research. In this setting, you have a set of items (subgoals), each with a weight (steps) and a value. You must select a subset of these items such that the total weight does not exceed a given capacity (budget), while maximizing the total value. The "0/1" designation means each item can either be taken or left behind; fractional selection is not allowed.

The problem is NP-hard in its general form, meaning no known polynomial-time algorithm solves all instances optimally. However, when the budget (capacity) is a reasonably bounded integer, dynamic programming provides an efficient pseudo-polynomial solution. The key insight is that the optimal substructure allows us to build up solutions for smaller budgets and smaller subsets of items, reusing previously computed results.

In the context of AI agents, this models planning under resource constraints: an agent must decide which subgoals to pursue given a finite action budget, prioritizing high-value, low-cost objectives. This greedy-like intuition (pick the best value-per-step) fails for 0/1 knapsack because local optimality does not guarantee global optimality, making DP necessary for correctness.

2. Algorithm Approach

Use bottom-up dynamic programming with a 1D array to optimize space.

Define dp[j] as the maximum value achievable using a budget of exactly j steps (or at most j, depending on formulation).
Initialize dp with zeros for all budget values from 0 to budget.
Iterate over each subgoal. For each subgoal with cost w and value v, update the dp array in reverse order (from budget down to w). This reverse iteration ensures each subgoal is used at most once (0/1 constraint).
The recurrence is:

dp[j] = \max(dp[j],\ dp[j - w] + v)

for all $j \geq w$ .

After processing all subgoals, dp[budget] holds the maximum total value.

The reverse iteration is critical: if you iterate forward, you risk using the same subgoal multiple times (converting it into an unbounded knapsack).

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results