Knapsack Budgeting

A Ruby-based solver that reframes participatory budgeting as the knapsack problem. Instead of letting citizens manually distribute a budget, this tool optimizes item selection based on expressed values.

How it works

1. Citizens rate how valuable each item/idea is (value score)
2. The solver finds the optimal combination of items that maximizes total value while staying within budget
3. Returns the top 3 near-optimal solutions for consideration

Requirements

• Ruby 3.x
• Bundler

Installation

bundle install

Usage

bundle exec rake 'knapsack:solve[path/to/items.csv,budget]'

Example

bundle exec rake 'knapsack:solve[example_items.csv,1000]'

CSV Format

The input CSV must have the following columns:

Column	Description
Item	Name of the item/idea
Value	How valuable the item is (integer)
Cost	Cost of the item (integer)

Example:

Item,Value,Cost
Park renovation,8,5000
New playground,9,3000
Street lighting,7,2000

Output

The solver returns the top 3 solutions, each showing:

• Total value achieved
• Total cost vs. budget
• List of selected items with their individual values and costs