node-red-contrib-knapsack

node-red-contrib-knapsack is a Node-RED module that provides a node to solve the 0/1 Knapsack problem. This module helps users optimize allocation of items within a limited capacity constraint while maximizing the total value.

Installation

Install the node-red-contrib-knapsack module using the following command in your Node-RED user directory (usually ~/.node-red):

npm install node-red-contrib-knapsack

After installation, the knapsack node will be available in the Node-RED palette under the "function" category.

Usage

The knapsack node accepts an array of objects representing items, each with a value and weight property, and a maximum capacity constraint.

Input

The input message should have the following structure:

msg.payload = {
  items: [
    { value: <number>, weight: <number> },
    ...
  ],
  capacity: <number>
};

• items: An array of objects, where each object represents an item with a value (positive number) and a weight (positive number).
• capacity: A positive number representing the maximum capacity constraint.

Output

The output message will have the following structure:

msg.payload = {
  maxValue: <number>,
  selectedItems: [
    { value: <number>, weight: <number> },
    ...
  ]
};

• maxValue: The maximum total value of the selected items within the capacity constraint.
• selectedItems: An array of objects representing the selected items to include in the knapsack.

Example

1. Drag and drop an inject node onto the Node-RED canvas.
2. Double-click the inject node to open its configuration window, and configure the payload as follows:

{
  "items": [
    { "value": 60, "weight": 10 },
    { "value": 100, "weight": 20 },
    { "value": 120, "weight": 30 }
  ],
  "capacity": 50
}

3. Drag and drop the knapsack node onto the canvas and connect it to the inject node.
4. Drag and drop a debug node onto the canvas and connect it to the knapsack node.
5. Deploy the flow.
6. Click on the inject node's button to send the input message. The debug node will display the output message with the maximum value and selected items.

License

GPL-3.0

Contributing

Contributions to node-red-contrib-knapsack are welcome. Please follow the standard guidelines for contributing to open-source projects, and make sure to test your changes before submitting a pull request.

Author

node-red-contrib-knapsack is written by Harshad Joshi