Skip to content

Instantly share code, notes, and snippets.

@shshemi

shshemi/notebook.ipynb

Last active February 3, 2024 23:44
Show Gist options
  • Save shshemi/a16893b885bb2b31da9c9839619e5a65 to your computer and use it in GitHub Desktop.
Save shshemi/a16893b885bb2b31da9c9839619e5a65 to your computer and use it in GitHub Desktop.
Download ZIP
Solving the knapsack problem using neural networks
Display the source blob
Display the rendered blob
Raw
notebook.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Neural Knapsack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### What is the knapsack problem?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is how my lovely computer algorithm professor explained the knapsack problem to me:\n",
"\n",
"Imagine a thief on a robbery, there are a couple of items to choose from where each item has its weight and value. The thief has a knapsack with a determined capacity and the thief can't carry items more than the capacity of his(or her) knapsack(the sum of chosen items' weights must be less than or equal to the knapsack's capacity). Our goal is to maximize the thief's profit by choosing the right items.\n",
"\n",
"But according to wikipedia [1]:\n",
"\n",
"\"Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items\".\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### What are we trying to do?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We want to somehow manage to solve the knapsack problem using the neural networks only."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Imports"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before we begin, we need to import the necessary libraries."
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"from keras.models import Model\n",
"from keras.layers import Dense, Activation, Lambda, Input, Concatenate, Multiply\n",
"from keras.metrics import binary_accuracy\n",
"from keras.losses import binary_crossentropy\n",
"import keras.backend as K"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Problem creation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"At first, we need to create some knapsack problems. We use random integers for items' weights, items' prices and the capacity of the knapsack. Along with each problem, we use brute force to find the optimum answer to the problem as the number of items in each problem is small enough."
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [],
"source": [
"def test_knapsack(x_weights, x_prices, x_capacity, picks):\n",
" total_price = np.dot(x_prices, picks)\n",
" total_weight = np.dot(x_weights, picks)\n",
" return total_price, max(total_weight - x_capacity, 0)\n",
"\n",
"\n",
"def brute_force_knapsack(x_weights, x_prices, x_capacity):\n",
" picks_space = 2 ** x_weights.shape[0]\n",
" best_price = 0\n",
" best_picks = None\n",
" for p in range(picks_space):\n",
" picks = np.zeros((x_weights.shape[0]))\n",
" for i, c in enumerate(\"{0:b}\".format(p)[::-1]):\n",
" picks[i] = c\n",
" price, violation = test_knapsack(x_weights, x_prices, x_capacity, picks)\n",
" if violation == 0:\n",
" if price > best_price:\n",
" best_price = price\n",
" best_picks = picks\n",
" return best_price, best_picks\n",
"\n",
"def create_knapsack(item_count=5):\n",
" x_weights = np.random.randint(1, 15, item_count)\n",
" x_prices = np.random.randint(1, 10, item_count)\n",
" x_capacity = np.random.randint(15, 50)\n",
" _, y_best_picks = brute_force_knapsack(x_weights, x_prices, x_capacity)\n",
" return x_weights, x_prices, x_capacity, y_best_picks"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Each of the knapsack problems is shown like this:"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Weights: [13 10 13 7 2]\n",
"Prices: [8 7 9 6 4]\n",
"Capacity: 27\n",
"Best picks: [0. 1. 1. 0. 1.]\n"
]
}
],
"source": [
"x_weights, x_prices, x_capacity, y_best_picks = create_knapsack()\n",
"print(\"Weights:\", x_weights)\n",
"print(\"Prices:\", x_prices)\n",
"print(\"Capacity:\", x_capacity)\n",
"print(\"Best picks:\", y_best_picks)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Metrics"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Beside binary classification accuracy(which compares the models' picks and optimum answer), knapsack problem needs a couple of other metrics to be evaluated with. The first metric I want to present is called \"overpricing\" as its name suggests, it shows the average difference between the price that the neural net has picked and the price of the optimum answer. It is called overpricing dude to the fact that the neural net most of the times becomes greedy and picks more than the optimum answer. Overpricing is defined in Keras framework as follow:"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [],
"source": [
"def metric_overprice(input_prices):\n",
" def overpricing(y_true, y_pred):\n",
" y_pred = K.round(y_pred)\n",
" return K.mean(K.batch_dot(y_pred, input_prices, 1) - K.batch_dot(y_true, input_prices, 1))\n",
"\n",
" return overpricing"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Another metric that is important to our cause is the amount of space that is used over the amount of actual capacity of the knapsack. The metric \"space violation\" is the difference between picked items required space and knapsacks capacity for positive values(when NN picked more than the capacity of knapsack) and zero for negative ones. Space violation is defined in Keras framework as follow:"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [],
"source": [
"def metric_space_violation(input_weights, input_capacity):\n",
" def space_violation(y_true, y_pred):\n",
" y_pred = K.round(y_pred)\n",
" return K.mean(K.maximum(K.batch_dot(y_pred, input_weights, 1) - input_capacity, 0))\n",
"\n",
" return space_violation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The last metric, I choose for knapsack problem is called \"pick count\". This variable shows the number of items that the neural net picks more/less than the optimum solution. The metric could be defined in Keras like:"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [],
"source": [
"def metric_pick_count():\n",
" def pick_count(y_true, y_pred):\n",
" y_pred = K.round(y_pred)\n",
" return K.mean(K.sum(y_pred, -1) - K.sum(y_true, -1))\n",
"\n",
" return pick_count"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Solutions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Dataset"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"First, we create a dataset consist of ten thousand of knapsack samples for training and two hundred for testing."
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [],
"source": [
"def create_knapsack_dataset(count, item_count=5):\n",
" x = [[], [], []]\n",
" y = [[]]\n",
" for _ in range(count):\n",
" p = create_knapsack(item_count)\n",
" x[0].append(p[0])\n",
" x[1].append(p[1])\n",
" x[2].append(p[2])\n",
" y[0].append(p[3])\n",
" return x, y\n",
"train_x, train_y = create_knapsack_dataset(10000)\n",
"test_x, test_y = create_knapsack_dataset(200)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we create a function to train our models for the sake of simplicity. The function is defind like:"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [],
"source": [
"def train_knapsack(model):\n",
" from keras.callbacks import ModelCheckpoint\n",
" import os\n",
" if os.path.exists(\"best_model.h5\"): os.remove(\"best_model.h5\")\n",
" model.fit(train_x, train_y, epochs=96, verbose=0, callbacks=[ModelCheckpoint(\"best_model.h5\", monitor=\"loss\", save_best_only=True, save_weights_only=True)])\n",
" model.load_weights(\"best_model.h5\")\n",
" train_results = model.evaluate(train_x, train_y, 64, 0)\n",
" test_results = model.evaluate(test_x, test_y, 64, 0)\n",
" print(\"Model results(Train/Test):\")\n",
" print(f\"Loss: {train_results[0]:.2f} / {test_results[0]:.2f}\")\n",
" print(f\"Binary accuracy: {train_results[1]:.2f} / {test_results[1]:.2f}\")\n",
" print(f\"Space violation: {train_results[2]:.2f} / {test_results[2]:.2f}\")\n",
" print(f\"Overpricing: {train_results[3]:.2f} / {test_results[3]:.2f}\")\n",
" print(f\"Pick count: {train_results[4]:.2f} / {test_results[4]:.2f}\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The function trains a neural knapsack model and prints its loss and metrics that we have discussed before."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Supervised continues solution"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The first solution that pops up to mind is to input three variables and expect the model to learn the picks(selected items) as the output and train the model using cross entropy loss. Since the output of the model is not discrete(only 0 and 1), we name it the supervised continuous model."
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Model results(Train/Test):\n",
"Loss: 0.25 / 0.26\n",
"Binary accuracy: 0.88 / 0.88\n",
"Space violation: 1.39 / 1.66\n",
"Overpricing: 0.56 / 0.67\n",
"Pick count: 0.06 / 0.08\n"
]
}
],
"source": [
"def supervised_continues_knapsack(item_count=5):\n",
" input_weights = Input((item_count,))\n",
" input_prices = Input((item_count,))\n",
" input_capacity = Input((1,))\n",
" inputs_concat = Concatenate()([input_weights, input_prices, input_capacity])\n",
" picks = Dense(item_count, use_bias=False, activation=\"sigmoid\")(inputs_concat)\n",
" model = Model(inputs=[input_weights, input_prices, input_capacity], outputs=[picks])\n",
" model.compile(\"sgd\",\n",
" binary_crossentropy,\n",
" metrics=[binary_accuracy, metric_space_violation(input_weights, input_capacity),\n",
" metric_overprice(input_prices), metric_pick_count()])\n",
" return model\n",
"model = supervised_continues_knapsack()\n",
"train_knapsack(model)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As it is expected, we can get slightly better accuracy by adding a hidden layer."
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Model results(Train/Test):\n",
"Loss: 0.23 / 0.23\n",
"Binary accuracy: 0.90 / 0.90\n",
"Space violation: 1.11 / 1.50\n",
"Overpricing: 0.70 / 0.85\n",
"Pick count: 0.12 / 0.15\n"
]
}
],
"source": [
"def supervised_continues_knapsack_one_hidden(item_count=5):\n",
" input_weights = Input((item_count,))\n",
" input_prices = Input((item_count,))\n",
" input_capacity = Input((1,))\n",
" inputs_concat = Concatenate()([input_weights, input_prices, input_capacity])\n",
" picks = Dense(item_count * 10, use_bias=False, activation=\"sigmoid\")(inputs_concat)\n",
" picks = Dense(item_count, use_bias=False, activation=\"sigmoid\")(picks)\n",
" model = Model(inputs=[input_weights, input_prices, input_capacity], outputs=[picks])\n",
" model.compile(\"sgd\",\n",
" binary_crossentropy,\n",
" metrics=[binary_accuracy, metric_space_violation(input_weights, input_capacity),\n",
" metric_overprice(input_prices), metric_pick_count()])\n",
" return model\n",
"model = supervised_continues_knapsack_one_hidden()\n",
"train_knapsack(model)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It can be inferred that the neural network is able to learn and generalize the knapsack problem. But there are a couple of problems with the supervised continuous approach:\n",
"* The output of the model is continuous however our picks must be discrete.\n",
"* The optimum answer is mandatory for training though it takes a reasonable amount of time to compute each.\n",
"* We can't trade off between space violation and overpricing.\n",
"\n",
"Through the rest of this article, we try to address these problems."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Supervised discrete solution"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can make the output of the model discrete by passing it through a round function. The problem is raised when we attempt to train the model as the gradient is not able to pass through the round function hence our model will not be trainable. So, we need a continues function which outputs only ones and zeros! We can make some compromises due to the fact that the mentioned function is not available in math yet. We can make the values so close to zero or one that the final result won't differ that much from actual one or zero. As described by [2], we can achieve the values close to -1, 0 or 1 by multiplying the output of two parallel fully-connected layers with $tanh$ and $sigmoid$ activations(more information could be obtained from the original paper). As we don't want -1 to be a possible value for the output, we use $$f(x)=(tanh(W_1 \\cdot x) + \\sigma(W_2 \\cdot x))^2$$where $W_1$ and $W_2$ are weight matrices."
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Model results(Train/Test):\n",
"Loss: 0.26 / 0.27\n",
"Binary accuracy: 0.88 / 0.88\n",
"Space violation: 1.82 / 2.21\n",
"Overpricing: 0.96 / 1.19\n",
"Pick count: 0.16 / 0.23\n"
]
}
],
"source": [
"def supervised_discrete_knapsack(item_count=5):\n",
" input_weights = Input((item_count,))\n",
" input_prices = Input((item_count,))\n",
" input_capacity = Input((1,))\n",
" inputs_concat = Concatenate()([input_weights, input_prices, input_capacity])\n",
" concat_tanh = Dense(item_count, use_bias=False, activation=\"tanh\")(inputs_concat)\n",
" concat_sigmoid = Dense(item_count, use_bias=False, activation=\"sigmoid\")(inputs_concat)\n",
" concat_multiply = Multiply()([concat_sigmoid, concat_tanh])\n",
" picks = Multiply()([concat_multiply, concat_multiply])\n",
" model = Model(inputs=[input_weights, input_prices, input_capacity], outputs=[picks])\n",
" model.compile(\"sgd\",\n",
" binary_crossentropy,\n",
" metrics=[binary_accuracy, metric_space_violation(input_weights, input_capacity),\n",
" metric_overprice(input_prices), metric_pick_count()])\n",
" return model\n",
"\n",
"model = supervised_discrete_knapsack()\n",
"train_knapsack(model)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We tackled the first problem by introducing a new model which outputs semi-discrete values. In order to handle the other problems, we need to introduce a new way of training and loss function."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Unsupervised discrete solution"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As we want to train our model without computing the optimum answer, we need a new loss function to train our neural knapsack models. The new loss function should not be in need of target outputs.\n",
"So we subsequently define the $w$, $p$, $c$ and $o$ as items' weights, items' prices, knapsack's capacity and model's output(picks). The first need of the knapsack problem is maximizing the picked items total price. The total price may be calculated via $$TotalPrice=p \\cdot o$$\n",
"\n",
"Meanwhile we want our picks not to surpass the knapsack's capacity. This value may be formulated like$$SpaceViolation=\\max{(w \\cdot o - c,\\ 0)}$$\n",
"\n",
"\n",
"Finally, we want to maximize the $TotalPrice$ while minimizing $SpaceViolation$. This could be formulated like:$$J=-TotalPrice + SpaceViolation$$\n",
"\n",
"\n",
"In order to be familiar with popular loss, we set our first term as the optimization term and the second one as the regularization term. With that in mind, we can add the $\\lambda$ coefficient for the regularization term. The final loss formula is $$J=-TotalPrice + \\lambda SpaceViolation$$\n",
"\n",
"\n",
"We can implement the new loss in Keras like this:"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [],
"source": [
"def knapsack_loss(input_weights, input_prices, input_capacity, cvc=1):\n",
" def loss(y_true, y_pred):\n",
" picks = y_pred\n",
" return (-1 * K.batch_dot(picks, input_prices, 1)) + cvc * K.maximum(\n",
" K.batch_dot(picks, input_weights, 1) - input_capacity, 0)\n",
" return loss"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using this loss function, we hope to train the neural network in an unsupervised fashion."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Note 1:** The $\\lambda$ parameter is named *cvc* in the Keras implementation of knapsack loss."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Note 2:** Although we received the expected output(y_true), we do not use it for computing the loss function. We can't either omit the argument as it is a Keras constraint to receive both predicted and expected outputs in loss functions."
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Model results(Train/Test):\n",
"Loss: -20.24 / -20.04\n",
"Binary accuracy: 0.84 / 0.85\n",
"Space violation: 2.44 / 2.48\n",
"Overpricing: 1.04 / 1.16\n",
"Pick count: 0.34 / 0.36\n"
]
}
],
"source": [
"def unsupervised_discrete_knapsack(item_count=5):\n",
" input_weights = Input((item_count,))\n",
" input_prices = Input((item_count,))\n",
" input_capacity = Input((1,))\n",
" inputs_concat = Concatenate()([input_weights, input_prices, input_capacity])\n",
" concat_tanh = Dense(item_count, use_bias=False, activation=\"tanh\")(inputs_concat)\n",
" concat_sigmoid = Dense(item_count, use_bias=False, activation=\"sigmoid\")(inputs_concat)\n",
" concat_multiply = Multiply()([concat_sigmoid, concat_tanh])\n",
" picks = Multiply()([concat_multiply, concat_multiply])\n",
" model = Model(inputs=[input_weights, input_prices, input_capacity], outputs=[picks])\n",
" model.compile(\"sgd\",\n",
" knapsack_loss(input_weights, input_prices, input_capacity, 1),\n",
" metrics=[binary_accuracy, metric_space_violation(input_weights, input_capacity),\n",
" metric_overprice(input_prices), metric_pick_count()])\n",
" return model\n",
"model = unsupervised_discrete_knapsack()\n",
"train_knapsack(model)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We experienced a 3 percent loss in binary accuracy method in comparison to the supervised model. We can address this problem by adding a hidden layer."
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Model results(Train/Test):\n",
"Loss: -21.79 / -21.49\n",
"Binary accuracy: 0.90 / 0.89\n",
"Space violation: 1.51 / 1.77\n",
"Overpricing: 1.24 / 1.41\n",
"Pick count: 0.28 / 0.30\n"
]
}
],
"source": [
"def unsupervised_discrete_knapsack_one_hidden(item_count=5):\n",
" input_weights = Input((item_count,))\n",
" input_prices = Input((item_count,))\n",
" input_capacity = Input((1,))\n",
" inputs_concat = Concatenate()([input_weights, input_prices, input_capacity])\n",
" inputs_concat = Dense(item_count * 10, activation=\"relu\")(inputs_concat)\n",
" concat_tanh = Dense(item_count, use_bias=False, activation=\"tanh\")(inputs_concat)\n",
" concat_sigmoid = Dense(item_count, use_bias=False, activation=\"sigmoid\")(inputs_concat)\n",
" concat_multiply = Multiply()([concat_sigmoid, concat_tanh])\n",
" picks = Multiply()([concat_multiply, concat_multiply])\n",
" model = Model(inputs=[input_weights, input_prices, input_capacity], outputs=[picks])\n",
" model.compile(\"sgd\",\n",
" knapsack_loss(input_weights, input_prices, input_capacity),\n",
" metrics=[binary_accuracy, metric_space_violation(input_weights, input_capacity),\n",
" metric_overprice(input_prices), metric_pick_count()])\n",
" return model\n",
"model = unsupervised_discrete_knapsack_one_hidden()\n",
"train_knapsack(model)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"By increasing the *cvc*($\\lambda$) parameter of the lost function, we can force the neural network not to violate the space of the knapsack."
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Model results(Train/Test):\n",
"Loss: -20.02 / -19.59\n",
"Binary accuracy: 0.87 / 0.86\n",
"Space violation: 0.23 / 0.24\n",
"Overpricing: -1.05 / -1.20\n",
"Pick count: -0.22 / -0.23\n"
]
}
],
"source": [
"def unsupervised_discrete_knapsack_one_hidden(item_count=5):\n",
" input_weights = Input((item_count,))\n",
" input_prices = Input((item_count,))\n",
" input_capacity = Input((1,))\n",
" inputs_concat = Concatenate()([input_weights, input_prices, input_capacity])\n",
" inputs_concat = Dense(item_count * 10, activation=\"relu\")(inputs_concat)\n",
" concat_tanh = Dense(item_count, use_bias=False, activation=\"tanh\")(inputs_concat)\n",
" concat_sigmoid = Dense(item_count, use_bias=False, activation=\"sigmoid\")(inputs_concat)\n",
" concat_multiply = Multiply()([concat_sigmoid, concat_tanh])\n",
" picks = Multiply()([concat_multiply, concat_multiply])\n",
" model = Model(inputs=[input_weights, input_prices, input_capacity], outputs=[picks])\n",
" model.compile(\"sgd\",\n",
" knapsack_loss(input_weights, input_prices, input_capacity, 5),\n",
" metrics=[binary_accuracy, metric_space_violation(input_weights, input_capacity),\n",
" metric_overprice(input_prices), metric_pick_count()])\n",
" return model\n",
"model = unsupervised_discrete_knapsack_one_hidden()\n",
"train_knapsack(model)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As demonstrated in the above experience, the space violation is reduced by $88\\%$ while losing only $3\\%$ of binary accuracy."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Conclusion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As discussed before, we solved the problem of knapsack using neural networks while the gradient can pass through the network. So our model can be trained end to end using any variation of the backpropagation algorithm.\n",
"\n",
"This research can be used in recommender systems, especially the ones which can recommend multiple items while maintaining space usage (banner Ads could be a good example)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## References\n",
"[1] Knapsack problem - Wikipedia, [Wikipedia.com](https://en.wikipedia.org/wiki/Knapsack_problem), July 2019\n",
"\n",
"[2] A. Trask, F. Hill, S. E. Reed, J. Rae, C. Dyer, and P. Blunsom, “Neural arithmetic logic units,” in Advances in Neural Information Processing Sys- tems, 2018, pp. 8035–8044. [Arxiv.org](https://arxiv.org/abs/1808.00508)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.8"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment