+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "A couple of greedy attempts. The first tries to pack the items by weight, always putting in the lightest items first.\n",
+ "\n",
+ "The second tries to be a bit more clever and sorts the items by pennies-per-kilo, so the highest-value bags are placed first."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def greedy_value_w(elements, weight_limit):\n",
+ " return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n",
+ " itertools.accumulate(\n",
+ " sorted((e for e in elements), key=lambda e: e['weight']),\n",
+ " lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n",
+ " )[-1]['value']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def greedy_value_vpw(elements, weight_limit):\n",
+ " return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n",
+ " itertools.accumulate(\n",
+ " sorted((e for e in elements), key=lambda e: e['value'] / e['weight'], reverse=True),\n",
+ " lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n",
+ " )[-1]['value']"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Utilities\n",
+ "A couple of functions for displaying the results. Only try these on the small example in the question, as otherwise there won't be enough screen area to display the table!"
+ ]
+ },