Knapsack - dedicated solver

Problem: choose the most valuable subset of items without exceeding the knapsack weight capacity.

Show code

import {
  initKnapsack,
  KnapsackSolver,
  KnapsackSolverType,
  setWorkerBridgeEnabled,
} from 'or-tools-wasm/knapsack';

setWorkerBridgeEnabled(true);
await initKnapsack();

const values = [
  360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
  78, 256,
];
const weights = [[
  7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42,
], [
  12, 4, 38, 20, 55, 45, 9, 52, 41, 35, 48, 16, 8, 22, 6, 12, 10, 28,
]];
const capacities = [240, 150];

const solver = new KnapsackSolver(
  KnapsackSolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
  'KnapsackExample',
);
solver.init(values, weights, capacities);

const computedValue = await solver.solve();
const packedItems = values
  .map((_, item) => item)
  .filter((item) => solver.best_solution_contains(item));

console.log(computedValue, packedItems);

Each item is a column; edit the cells to change the model before solving.
The value row is what the solver maximizes.
Each resource row is something selected items consume, such as weight, volume, time, or budget.
The capacity cell at the right is the limit for that resource.
Add a resource when the same items must satisfy another limit at the same time.
After solving, selected item columns are highlighted and the solution reports total value, packed item ids, and resource usage.

Use worker bridge

Solution

Run the solver to view the solution.

Status: