Google Git
Sign in
apache / groovy-dev-site / 4280b2fb449f2f7aaa62875e1c469416ec4d7a33 / . / blog / groovy-knapsack.html
blob: 54b6e87af2df673571ea5db9b9ecad538cd79e52 [file] [log] [blame]
<!DOCTYPE html>
<!--[if lt IE 7]> <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]-->
<!--[if IE 7]> <html class="no-js lt-ie9 lt-ie8"> <![endif]-->
<!--[if IE 8]> <html class="no-js lt-ie9"> <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js"> <!--<![endif]--><head>
<meta charset='utf-8'/><meta http-equiv='X-UA-Compatible' content='IE=edge'/><meta name='viewport' content='width=device-width, initial-scale=1'/><meta name='keywords' content='knapsack, optimisation'/><meta name='description' content='This post looks at solving the knapsack problem with Groovy.'/><title>The Apache Groovy programming language - Blogs - Solving the Knapsack Problem with Groovy</title><link href='../img/favicon.ico' type='image/x-ico' rel='icon'/><link rel='stylesheet' type='text/css' href='../css/bootstrap.css'/><link rel='stylesheet' type='text/css' href='../css/font-awesome.min.css'/><link rel='stylesheet' type='text/css' href='../css/style.css'/><link rel='stylesheet' type='text/css' href='https://cdnjs.cloudflare.com/ajax/libs/prettify/r298/prettify.min.css'/>
</head><body>
<div id='fork-me'>
<a href='https://github.com/apache/groovy'>
<img style='position: fixed; top: 20px; right: -58px; border: 0; z-index: 100; transform: rotate(45deg);' src='/img/horizontal-github-ribbon.png'/>
</a>
</div><div id='st-container' class='st-container st-effect-9'>
<nav class='st-menu st-effect-9' id='menu-12'>
<h2 class='icon icon-lab'>Socialize</h2><ul>
<li>
<a href='https://groovy-lang.org/mailing-lists.html' class='icon'><span class='fa fa-envelope'></span> Discuss on the mailing-list</a>
</li><li>
<a href='https://twitter.com/ApacheGroovy' class='icon'><span class='fa fa-twitter'></span> Groovy on Twitter</a>
</li><li>
<a href='https://groovy-lang.org/events.html' class='icon'><span class='fa fa-calendar'></span> Events and conferences</a>
</li><li>
<a href='https://github.com/apache/groovy' class='icon'><span class='fa fa-github'></span> Source code on GitHub</a>
</li><li>
<a href='https://groovy-lang.org/reporting-issues.html' class='icon'><span class='fa fa-bug'></span> Report issues in Jira</a>
</li><li>
<a href='http://stackoverflow.com/questions/tagged/groovy' class='icon'><span class='fa fa-stack-overflow'></span> Stack Overflow questions</a>
</li><li>
<a href='http://groovycommunity.com/' class='icon'><span class='fa fa-slack'></span> Slack Community</a>
</li>
</ul>
</nav><div class='st-pusher'>
<div class='st-content'>
<div class='st-content-inner'>
<!--[if lt IE 7]>
<p class="browsehappy">You are using an <strong>outdated</strong> browser. Please <a href="http://browsehappy.com/">upgrade your browser</a> to improve your experience.</p>
<![endif]--><div><div class='navbar navbar-default navbar-static-top' role='navigation'>
<div class='container'>
<div class='navbar-header'>
<button type='button' class='navbar-toggle' data-toggle='collapse' data-target='.navbar-collapse'>
<span class='sr-only'></span><span class='icon-bar'></span><span class='icon-bar'></span><span class='icon-bar'></span>
</button><a class='navbar-brand' href='../index.html'>
<i class='fa fa-star'></i> Apache Groovy
</a>
</div><div class='navbar-collapse collapse'>
<ul class='nav navbar-nav navbar-right'>
<li class=''><a href='https://groovy-lang.org/learn.html'>Learn</a></li><li class=''><a href='https://groovy-lang.org/documentation.html'>Documentation</a></li><li class=''><a href='/download.html'>Download</a></li><li class=''><a href='https://groovy-lang.org/support.html'>Support</a></li><li class=''><a href='/'>Contribute</a></li><li class=''><a href='https://groovy-lang.org/ecosystem.html'>Ecosystem</a></li><li class=''><a href='/blog'>Blog posts</a></li><li class=''><a href='https://groovy.apache.org/events.html'></a></li><li>
<a data-effect='st-effect-9' class='st-trigger' href='#'>Socialize</a>
</li><li class=''>
<a href='../search.html'>
<i class='fa fa-search'></i>
</a>
</li>
</ul>
</div>
</div>
</div><div id='content' class='page-1'><div class='row'><div class='row-fluid'><div class='col-lg-3'><ul class='nav-sidebar'><li><a href='./'>Blog index</a></li><li class='active'><a href='#doc'>Solving the Knapsack Problem with Groovy</a></li><li><a href='#_case_study' class='anchor-link'>Case Study</a></li><li><a href='#_brute_force' class='anchor-link'>Brute force</a></li><li><a href='#_using_branch_and_bound' class='anchor-link'>Using Branch and Bound</a></li><li><a href='#_using_dynamic_programming' class='anchor-link'>Using Dynamic Programming</a></li><li><a href='#_using_bitsets' class='anchor-link'>Using BitSets</a></li><li><a href='#_using_constraint_programming' class='anchor-link'>Using Constraint Programming</a></li><li><a href='#_using_ortools' class='anchor-link'>Using OrTools</a></li><li><a href='#_using_jenetics' class='anchor-link'>Using Jenetics</a></li><li><a href='#_using_greedy_selection' class='anchor-link'>Using Greedy selection</a></li><li><a href='#_further_information' class='anchor-link'>Further information</a></li><li><a href='#_conclusion' class='anchor-link'>Conclusion</a></li></ul></div><div class='col-lg-8 col-lg-pull-0'><a name='doc'></a><h1>Solving the Knapsack Problem with Groovy</h1><p><span>Author: <i>Paul King</i></span><br/><span>Published: 2024-02-03 08:08PM</span></p><hr/><div id="preamble">
<div class="sectionbody">
<div class="paragraph">
<p>The
<a href="https://en.wikipedia.org/wiki/Knapsack_problem">knapsack problem</a>
is a problem in combinatorial optimization.
Given a set of items, each of a given weight and value,
determine which items to place into a knapsack (or other container)
in order to maximise the value within the knapsack without exceeding
a given weight limit.</p>
</div>
<div class="paragraph">
<p><span class="image"><img src="img/knapsack2.jpg" alt="A knapsack and some gems"></span></p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_case_study">Case Study</h2>
<div class="sectionbody">
<div class="paragraph">
<p>For our case study, we&#8217;ll start with placing gems within the
knapsack. The gems have the following characteristics:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 33.3333%;">
<col style="width: 33.3333%;">
<col style="width: 33.3334%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top">Index&nbsp;</th>
<th class="tableblock halign-left valign-top">Weight&nbsp;</th>
<th class="tableblock halign-left valign-top">Value</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">10</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">15</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">17</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>The gem can either be in the knapsack or not.
This is known as the 0/1 knapsack variation of the problem.
We&#8217;ll look at some other variations later.</p>
</div>
<div class="paragraph">
<p>Our goal then is to find out which gems we place into the knapsack to maximise
the value.</p>
</div>
<div class="paragraph">
<p><span class="image"><img src="img/knapsack.jpg" alt="A knapsack and some gems"></span></p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_brute_force">Brute force</h2>
<div class="sectionbody">
<div class="paragraph">
<p>The first approach we might take is simply to try all
possible combinations, throwing away any which exceed
the weight limit, and then finding the maximum value of those that are left.</p>
</div>
<div class="paragraph">
<p>One way to do this is to generate all possible index combinations.
Then, select the ones which satisfy the knapsack weight constraint.
Then, find the one which yields the highest value as shown here:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
int W = 10
var totalValue = { it*.v.sum() }
var withinLimit = { it*.w.sum() &lt;= W }
var asTriple = { [i:it, w:weights[it], v:values[it]] }
var best = weights
.indices
.collect(asTriple)
.subsequences()
.findAll(withinLimit)
.max(totalValue)
println "Total value for capacity $W = ${totalValue(best)}"
println "Gems taken: ${best*.i}"
println "Gem weights: ${best*.w}"</code></pre>
</div>
</div>
<div class="paragraph">
<p>In a bit more detail, we first define three helper closures, <code>totalValue</code>, <code>withinLimit</code>,
and <code>asTriple</code>. Collecting our data into the list of maps (triples) isn&#8217;t required
but simplifies subsequent processing. Once we have our data, we find the
subsequences, retain the ones within the weight limit, and then find the maximum value.</p>
</div>
<div class="paragraph">
<p>Running this script yields the following output:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>Total value for capacity 10 = 30
Gems taken: [1, 2, 3]
Gem weights: [2, 3, 5]</pre>
</div>
</div>
<div class="paragraph">
<p>While this is simple enough, it doesn&#8217;t offer many opportunities
for optimisation. For a small problem like our case study,
optimisation is not important, but for larger problems,
the number of combinations may grow exponentially large,
and we&#8217;ll want to keep that in mind.</p>
</div>
<div class="paragraph">
<p>Let&#8217;s instead, consider a recursive solution which lets us opt out
earlier for cases which will exceed the maximum knapsack weight limit:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int solve(int[] w, int[] v, int W) {
knapsack(w, v, v.length, W)
}
int knapsack(int[] w, int[] v, int n, int W) {
if (n &lt;= 0) {
0
} else if (w[n - 1] &gt; W) {
knapsack(w, v, n - 1, W)
} else {
[knapsack(w, v, n - 1, W),
v[n - 1] + knapsack(w, v, n - 1, W - w[n - 1])].max()
}
}
int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
[6, 8, 10].each {
println "Total value for capacity $it = ${solve(weights, values, it)}"
}</code></pre>
</div>
</div>
<div class="paragraph">
<p>Here, we consider each gem (for a given stage, gem <code>n</code>, or index <code>n - 1</code>).
There are two paths to calculate, one with the gem <em>included</em>,
the other with it <em>excluded</em>. We remember the maximum value returned
from the two paths and continue processing. When a gem is included,
we then solve the smaller problem of fitting the remaining gems into a conceptually
smaller knapsack. If placing a gem into the knapsack causes the weight to exceed
the limit, then we can discard that path from further processing.</p>
</div>
<div class="paragraph">
<p>It is useful to visualize the above process as a solution tree (shown for capacity 10):</p>
</div>
<div class="listingblock">
<div class="content">
<pre>digraph unix {
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif"]
edge [fontname="Helvetica,Arial,sans-serif"]
node [color=lightblue2, style=filled];
n [label="0 0"]
n5 [label="6 17"]
n_ [label="0 0"]
n54 [label="11 _", color="#f88379"]
n_4 [label="5 15"]
n5_ [label="6 17"]
n__ [label="0 0"]
n5_3 [label="9 27"]
n5__ [label="6 17"]
n_43 [label="8 25"]
n_4_ [label="5 15"]
n__3 [label="3 10"]
n___ [label="0 0"]
n__32 [label="5 15"]
n___2 [label="2 5"]
n5_32 [label="11 _", color="#f88379"]
n5__2 [label="8 23"]
n_432 [label="10 30"]
n_4_2 [label="7 20"]
n__3_ [label="3 10"]
n____ [label="0 0"]
n5_3_ [label="9 27"]
n5___ [label="6 17"]
n_43_ [label="8 25"]
n_4__ [label="5 15"]
n__3_ [label="3 10"]
n____ [label="0 0"]
n__321 [label="6 16"]
n___21 [label="3 7"]
n5__21 [label="9 23"]
n_4321 [label="11 _", color="#f88379"]
n_4_21 [label="9 20"]
n__3_1 [label="4 11"]
n____1 [label="1 1"]
n5_3_1 [label="10 28"]
n5___1 [label="7 18"]
n_43_1 [label="9 26"]
n_4__1 [label="6 16"]
n__3_1 [label="4 11"]
n____1 [label="1 1"]
n__32_ [label="5 15"]
n___2_ [label="2 5"]
n5__2_ [label="8 23"]
n_432_ [label="10 30", color=gold]
n_4_2_ [label="7 20"]
n__3__ [label="3 10"]
n_____ [label="0 0"]
n5_3__ [label="9 27"]
n5____ [label="6 17"]
n_43__ [label="8 25"]
n_4___ [label="5 15"]
n__3__ [label="3 10"]
n_____ [label="0 0"]
n -&gt; n5 [label="Gem5"];
n -&gt; n_ [label=&lt;&lt;s&gt;Gem5&lt;/s&gt;&gt;];
n5 -&gt; n54 [label="Gem4"];
n5 -&gt; n5_ [label=&lt;&lt;s&gt;Gem4&lt;/s&gt;&gt;];
n_ -&gt; n_4 [label="Gem4"];
n_ -&gt; n__ [label=&lt;&lt;s&gt;Gem4&lt;/s&gt;&gt;];
n5_ -&gt; n5_3 [label="Gem3"];
n5_ -&gt; n5__ [label=&lt;&lt;s&gt;Gem3&lt;/s&gt;&gt;];
n_4 -&gt; n_43 [label="Gem3"];
n_4 -&gt; n_4_ [label=&lt;&lt;s&gt;Gem3&lt;/s&gt;&gt;];
n__ -&gt; n__3 [label="Gem3"];
n__ -&gt; n___ [label=&lt;&lt;s&gt;Gem3&lt;/s&gt;&gt;];
n5_3 -&gt; n5_32 [label="Gem2"];
n5_3 -&gt; n5_3_ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n_43 -&gt; n_432 [label="Gem2"];
n_43 -&gt; n_43_ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n__3 -&gt; n__32 [label="Gem2"];
n__3 -&gt; n__3_ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n5__ -&gt; n5__2 [label="Gem2"];
n5__ -&gt; n5___ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n_4_ -&gt; n_4_2 [label="Gem2"];
n_4_ -&gt; n_4__ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n___ -&gt; n___2 [label="Gem2"];
n___ -&gt; n____ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n_432 -&gt; n_4321 [label="Gem1"];
n_432 -&gt; n_432_ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n__32 -&gt; n__321 [label="Gem1"];
n__32 -&gt; n__32_ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n5__2 -&gt; n5__21 [label="Gem1"];
n5__2 -&gt; n5__2_ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n_4_2 -&gt; n_4_21 [label="Gem1"];
n_4_2 -&gt; n_4_2_ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n___2 -&gt; n___21 [label="Gem1"];
n___2 -&gt; n___2_ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n5_3_ -&gt; n5_3_1 [label="Gem1"];
n5_3_ -&gt; n5_3__ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n_43_ -&gt; n_43_1 [label="Gem1"];
n_43_ -&gt; n_43__ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n__3_ -&gt; n__3_1 [label="Gem1"];
n__3_ -&gt; n__3__ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n5___ -&gt; n5___1 [label="Gem1"];
n5___ -&gt; n5____ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n_4__ -&gt; n_4__1 [label="Gem1"];
n_4__ -&gt; n_4___ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n____ -&gt; n____1 [label="Gem1"];
n____ -&gt; n_____ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
}</pre>
</div>
</div>
<div class="paragraph">
<p>We calculate here the result for 3 different knapsack weight limits (6, 8, and 10).
The output looks like this:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>Total value for capacity 6 = 17
Total value for capacity 8 = 25
Total value for capacity 10 = 30</pre>
</div>
</div>
<div class="paragraph">
<p>Instead of having 32 combinations (2^5 for our 5 gems), we&#8217;ll only process 11,
16, and 21 combinations where both paths are traversed when the maximum weight
limit is 6, 8, and 10 respectively.</p>
</div>
<div class="paragraph">
<p>More importantly, we&#8217;ll have further possibilities for optimisation.
One quick win is to memoize (cache) the results of calling the <code>knapsack</code> method.
Groovy makes this easy. The only change from above is the addition of the <code>@Memoized</code> annotation:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">@Memoized
int knapsack(int[] w, int[] v, int n, int W) {
if (n &lt;= 0) {
0
} else if (w[n - 1] &gt; W) {
knapsack(w, v, n - 1, W)
} else {
[knapsack(w, v, n - 1, W),
v[n - 1] + knapsack(w, v, n - 1, W - w[n - 1])].max()
}
}</code></pre>
</div>
</div>
<div class="paragraph">
<p>Running this has the same result as before but the number of executions of
the <code>knapsack</code> method reduces from 44 to 32 (when just calculating for the knapsack of weight limit 10), and from 107 to 49 (when calculating for 6, 8, and 10).</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_using_branch_and_bound">Using Branch and Bound</h2>
<div class="sectionbody">
<div class="paragraph">
<p>Another technique often used for optimisation is branch and bound.
It&#8217;s a special form of the general principle of divide and conquer;
solving a big problem by turning it into smaller problems.</p>
</div>
<div class="paragraph">
<p>Divide and conquer is similar to what we did for the recursive solution above,
but with branch and bound, we perform smarter elimination.
Before processing the children of a branch, the branch is checked against
upper and lower estimated bounds of some optimal solution and is discarded
if it cannot produce a better solution. For the knapsack problem,
we could find an optimal "greedy" solution if we could use fractional</p>
</div>
<div class="paragraph">
<p>First, we&#8217;ll create an <code>Item</code> record for holding our weights and values.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">record Item(int weight, int value) {}</code></pre>
</div>
</div>
<div class="paragraph">
<p>Next, we&#8217;ll create a <code>Node</code> to hold information about the current status
of a candidate solution at a particular point in our solution tree:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">@Canonical
class Node {
int level, value, weight
public int bound
static Node next(Node parent) {
new Node(parent.level + 1, parent.value, parent.weight)
}
}</code></pre>
</div>
</div>
<div class="paragraph">
<p>Next, the <code>bound</code> method calculates the weight using the
optimal (greedy) algorithm. This would require us to allow fractional
parts of gems to be accurate, but in our case, we are just using it
as a bound. Think of estimating with best and worst case kept in mind.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int bound(Node u, int n, int W, List&lt;Item&gt; items) {
if (u.weight &gt;= W)
return 0
int valueBound = u.value
int j = u.level + 1
int totalWeight = u.weight
while (j &lt; n &amp;&amp; totalWeight + items[j].weight &lt;= W) {
totalWeight += items[j].weight
valueBound += items[j].value
j++
}
if (j &lt; n)
valueBound += (int) ((W - totalWeight) * items[j].value / items[j].weight)
valueBound
}</code></pre>
</div>
</div>
<div class="paragraph">
<p>Now, our knapsack method will sort the gems according to
most value per weight and then process through them keeping
track of the bound at each step.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int knapsack(int W, List&lt;Item&gt; items, int n) {
items.sort { it.value / it.weight }
var q = new PriorityQueue&lt;&gt;((a, b) -&gt; b.bound &lt;=&gt; a.bound)
Node u, v
q.offer(new Node(-1, 0, 0))
int bestValue = 0
while (q) {
u = q.poll()
if (u.level == n - 1)
continue
else
v = Node.next(u)
v.weight += items[v.level].weight
v.value += items[v.level].value
if (v.weight &lt;= W &amp;&amp; v.value &gt; bestValue)
bestValue = v.value
v.bound = bound(v, n, W, items)
if (v.bound &gt; bestValue)
q.offer(v)
v = Node.next(u)
v.bound = bound(v, n, W, items)
if (v.bound &gt; bestValue)
q.offer(v)
}
bestValue
}
int W = 10
int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
var items = values.indices.collect {
new Item(weights[it], values[it])
}
println "Total value for capacity $W = ${knapsack(W, items, values.length)}"</code></pre>
</div>
</div>
<div class="paragraph">
<p>Which has this visualization (for capacity 10):</p>
</div>
<div class="listingblock">
<div class="content">
<pre>digraph unix {
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif"]
edge [fontname="Helvetica,Arial,sans-serif"]
node [color=lightblue2, style=filled];
n [label="0 0 _ _"]
n3 [label="3 10 30 10"]
n_ [label="0 0 29 10"]
n34 [label="8 25 30 25"]
n_4 [label="5 15 29 25"]
n3_ [label="3 10 30 25"]
n__ [label="0 0 29 25"]
n345 [label="14 _ _ _", color="#f88379"]
n_45 [label="11 _ _ _", color="#f88379"]
n3_5 [label="9 27 30 25"]
n__5 [label="6 17 29 25"]
n34_ [label="8 25 30 25"]
n_4_ [label="5 15 29 25"]
n3__ [label="3 10 30 25"]
n___ [label="0 0 29 25"]
n3_52 [label="11 _ _ _", color="#f88379"]
n__52 [label="8 23 29 30", color="#cbc3e3"]
n34_2 [label="10 30 30 30"]
n_4_2 [label="7 20 29 30", color="#cbc3e3"]
n3__2 [label="5 15 30 30"]
n___2 [label="2 5 29 30", color="#cbc3e3"]
n3_5_ [label="9 27 30 30"]
n__5_ [label="6 17 29 30", color="#cbc3e3"]
n34__ [label="8 25 30 30"]
n_4__ [label="5 15 29 30", color="#cbc3e3"]
n3___ [label="3 10 30 30"]
n____ [label="0 0 29 30", color="#cbc3e3"]
n34_21 [label="11 _ _ _", color="#f88379"]
n3__21 [label="6 16 30 30"]
n3_5_1 [label="10 28 30 30"]
n34__1 [label="9 26 30 30"]
n3___1 [label="4 11 30 30"]
n34_2_ [label="10 30 30 30", color=gold]
n3__2_ [label="5 15 30 30"]
n3_5__ [label="9 27 30 30"]
n34___ [label="8 25 30 30"]
n3____ [label="3 10 30 30"]
n -&gt; n3 [label="Gem3"];
n -&gt; n_ [label=&lt;&lt;s&gt;Gem3&lt;/s&gt;&gt;];
n3 -&gt; n34 [label="Gem4"];
n_ -&gt; n_4 [label="Gem4"];
n3 -&gt; n3_ [label=&lt;&lt;s&gt;Gem4&lt;/s&gt;&gt;];
n_ -&gt; n__ [label=&lt;&lt;s&gt;Gem4&lt;/s&gt;&gt;];
n34 -&gt; n345 [label="Gem5"];
n_4 -&gt; n_45 [label="Gem5"];
n3_ -&gt; n3_5 [label="Gem5"];
n__ -&gt; n__5 [label="Gem5"];
n34 -&gt; n34_ [label=&lt;&lt;s&gt;Gem5&lt;/s&gt;&gt;];
n_4 -&gt; n_4_ [label=&lt;&lt;s&gt;Gem5&lt;/s&gt;&gt;];
n3_ -&gt; n3__ [label=&lt;&lt;s&gt;Gem5&lt;/s&gt;&gt;];
n__ -&gt; n___ [label=&lt;&lt;s&gt;Gem5&lt;/s&gt;&gt;];
n3_5 -&gt; n3_52 [label="Gem2"];
n__5 -&gt; n__52 [label="Gem2"];
n34_ -&gt; n34_2 [label="Gem2"];
n_4_ -&gt; n_4_2 [label="Gem2"];
n3__ -&gt; n3__2 [label="Gem2"];
n___ -&gt; n___2 [label="Gem2"];
n3_5 -&gt; n3_5_ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n__5 -&gt; n__5_ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n34_ -&gt; n34__ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n_4_ -&gt; n_4__ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n3__ -&gt; n3___ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n___ -&gt; n____ [label=&lt;&lt;s&gt;Gem2&lt;/s&gt;&gt;];
n34_2 -&gt; n34_21 [label="Gem1"];
n3__2 -&gt; n3__21 [label="Gem1"];
n3_5_ -&gt; n3_5_1 [label="Gem1"];
n34__ -&gt; n34__1 [label="Gem1"];
n3___ -&gt; n3___1 [label="Gem1"];
n34_2 -&gt; n34_2_ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n3__2 -&gt; n3__2_ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n3_5_ -&gt; n3_5__ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n34__ -&gt; n34___ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
n3___ -&gt; n3____ [label=&lt;&lt;s&gt;Gem1&lt;/s&gt;&gt;];
}</pre>
</div>
</div>
<div class="paragraph">
<p>We should note that as well as discarding the
infeasible paths which exceed the weight limit,
we now also discard unfruitful paths which our bound
value tells us can never exceed some alternative <em>best</em> path
we already know about.</p>
</div>
<div class="paragraph">
<p>It has the following output:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>Total value for capacity 10 = 30</pre>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_using_dynamic_programming">Using Dynamic Programming</h2>
<div class="sectionbody">
<div class="paragraph">
<p>You can think of dynamic programming as a special case of the
branch and bound technique. It can also be thought of as similar
to the memoization we looked at earlier. In this case, rather
than Groovy providing us with the cache, we track it ourselves
in the <code>dp</code> array:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int solve(int[] v, int[] w, int W) {
knapsack(new Integer[v.length][W+1], v, w, W, 0)
}
int knapsack(Integer[][] dp, int[] v, int[] w, int W, int n) {
if (W &lt;= 0 || n &gt;= v.length) {
return 0
}
if (dp[n][W]) {
return dp[n][W]
}
int tryN = w[n] &gt; W ? 0 : v[n] + knapsack(dp, v, w, W - w[n], n + 1)
int skipN = knapsack(dp, v, w, W, n + 1)
dp[n][W] = max(tryN, skipN)
}
int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
[6, 8, 10].each {
println "Total value for capacity $it = ${solve(values, weights, it)}"
}</code></pre>
</div>
</div>
<div class="listingblock">
<div class="content">
<pre>Total value for capacity 6 = 17
Total value for capacity 8 = 25
Total value for capacity 10 = 30</pre>
</div>
</div>
<div class="paragraph">
<p>Like with most things, we have options when using dynamic programming.
Here is an alternative variant which keeps a second array tracking
the gems taken:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
int W = 10
int N = values.length
int[][] dp = new int[N + 1][W + 1]
boolean[][] sol = new boolean[N + 1][W + 1]
for (int n = 1; n &lt;= N; n++) {
for (int w = 1; w &lt;= W; w++) {
int skipN = dp[n - 1][w]
int tryN = weights[n - 1] &gt; w ? 0 : values[n - 1] + dp[n - 1][w - weights[n - 1]]
dp[n][w] = max(skipN, tryN)
sol[n][w] = tryN &gt; skipN
}
}
println "Total value for capacity $W = ${dp[N][W]}"
def taken = []
for (int i = N, j = W; j &gt; 0; i--) {
if (sol[i][j]) {
taken &lt;&lt; i - 1
j -= weights[i - 1]
}
}
println "Gems taken: $taken"</code></pre>
</div>
</div>
<div class="paragraph">
<p>If just the final value is what we want to work out, our earlier
variant will be very slightly faster and use less memory.
If keeping track of the gems taken is important, then this
variant would be one way to go.</p>
</div>
<div class="paragraph">
<p>It produces the following output:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>Total value for capacity 10 = 30
Gems taken: [3, 2, 1]</pre>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_using_bitsets">Using BitSets</h2>
<div class="sectionbody">
<div class="paragraph">
<p>When using dynamic programming, our 2D <code>dp</code> array could
use significant memory for large problems. In such cases,
we could use a bitset instead of the array like this:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
int W = 10
var N = weights.size()
var nums = 0L..&lt;(1L &lt;&lt; N)
var totalValue = nums
.collect{ BitSet.valueOf(it) }
.findAll{ mask -&gt; mask.stream().map(idx -&gt; weights[idx]).reduce(0, Integer::sum) &lt;= W }
.collect{ mask -&gt; nums.indices.sum{ idx -&gt; mask[idx] ? values[idx] : 0 } }
.max()
println "Total value for capacity $W = $totalValue"</code></pre>
</div>
</div>
<div class="paragraph">
<p>Here we are using the bitset to track the gem combinations
in a candidate solution. This might seem a little unusual
but does the job in our case.</p>
</div>
<div class="paragraph">
<p>It has the following output:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>Total value for capacity 10 = 30</pre>
</div>
</div>
<div class="paragraph">
<p>Most often bitsets are used not just to save memory but
because for certain problems we can perform operations
on entire bitsets. You can think of this as bulk
operations with <em>free</em> parallelism when compared to performing
such operations on say arrays of booleans.</p>
</div>
<div class="paragraph">
<p>We can show a simple example of this kind of operation
by adding a preliminary optimisation step. We&#8217;ll use a simple
trick which can find all possible sums of a set of numbers
using bit shifting. If the maximum weight (10 in this example)
isn&#8217;t in the list of possible sums - we find that out using the
<code>maskW</code> constant, then we discard the combination.
For simplicity, we&#8217;ve kept the example simple here, but realise that this
crude optimisation has the possibility of ruling out valid candidates.
The maximum value could, in theory, be for weight 8 or 9 for instance.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
int W = 10
var N = weights.size()
var maskW = 1L &lt;&lt; W
var nums = 0L..&lt;(1L &lt;&lt; N)
var totalValue = nums
.collect{ BitSet.valueOf(it) }
.findAll{ mask -&gt; mask.stream().reduce(1) {a, b -&gt; a | a &lt;&lt; weights[b] } &amp; maskW }
.findAll{ mask -&gt; mask.stream().map(idx -&gt; weights[idx]).reduce(0, Integer::sum) &lt;= W }
.collect{ mask -&gt; nums.indices.sum{ idx -&gt; mask[idx] ? values[idx] : 0 } }
.max()
println "Total value for capacity $W = $totalValue"</code></pre>
</div>
</div>
<div class="paragraph">
<p>Which has the same output for this case study,
so luckily, our crude optimisation step didn&#8217;t reject the best solution.</p>
</div>
<div class="paragraph">
<p>Groovy 5 adds support for <code>&lt;&lt;</code> (left shift),<code>&gt;&gt;</code> (right shift),
and <code>&gt;&gt;&gt;</code> (right shift unsigned) operators for bitsets.
This kind of functionality will make working on such
problems even nicer with Groovy.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_using_constraint_programming">Using Constraint Programming</h2>
<div class="sectionbody">
<div class="paragraph">
<p>Another technique we could consider is constraint programming.
Here we define some constraints and let a solver find solutions
for us. Here we have used the Choco solver.</p>
</div>
<div class="paragraph">
<p>We thought we would also spice up the example and illustrate
what is known as the bounded knapsack problem. Instead of
either taking the gem or leaving it out, we now consider
gems to be readily available commodities and the weight and
value would apply to all gems of a particular type.</p>
</div>
<div class="paragraph">
<p>In our example, we&#8217;ll set the bound for our solver&#8217;s
domain variables to be between <code>0</code> and <code>W</code>.
We could easily set the upper bound to be <code>1</code> and
we&#8217;d be back to the 0/1 knapsack problem.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
int W = 10
int unbounded = 100000
var counts = new IntVar[values.length]
var found = false
new Model('KnapsackProblem').with {
counts.indices.each(i -&gt; counts[i] = intVar("count$i", 0, W))
scalar(counts, weights, '&lt;=', W).post()
var total = intVar("Total value for capacity $W (unbounded)", 0, unbounded)
scalar(counts, values, '=', total).post()
setObjective(MAXIMIZE, total)
while (solver.solve()) {
found = true
println "$total, $counts"
}
}
if (!found) println 'No solution'</code></pre>
</div>
</div>
<div class="paragraph">
<p>We keep an array <code>counts</code> of solver variables,
apply numerous constraints on the variables,
tell the solver to maximise the <code>total</code> variable.</p>
</div>
<div class="paragraph">
<p>When we run this script, it produces the following output:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>Total value for capacity 10 (unbounded) = 25, [count0 = 0, count1 = 5, count2 = 0, count3 = 0, count4 = 0]
Total value for capacity 10 (unbounded) = 30, [count0 = 0, count1 = 2, count2 = 2, count3 = 0, count4 = 0]
Total value for capacity 10 (unbounded) = 31, [count0 = 1, count1 = 0, count2 = 3, count3 = 0, count4 = 0]</pre>
</div>
</div>
<div class="paragraph">
<p>Here, the solver is finding solutions which satisfy the problem
as we have specified it, and then tries to find better solutions.
We should note that because we are allowing more than one of
each gem, it isn&#8217;t surprising that our answer (31) is higher
than our previous best answer (30).</p>
</div>
<div class="paragraph">
<p>If we didn&#8217;t want to receive all solutions, we can simply
ask for the best solution, or provide the solver with better
search hints for the problem, to arrive at the best answer earlier.</p>
</div>
<div class="paragraph">
<p>As it turns out, the set of constraints we set in place here to
solve the knapsack problem, are so common, that Choco has a
built-in <code>knapsack</code> method which sets multiple constraints
for us. We could use it as follows:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
int W = 10
int unbounded = 100000
var counts = new IntVar[values.length]
var found = false
new Model('KnapsackProblem').with {
counts.indices.each(i -&gt; counts[i] = intVar("count$i", 0, W))
var totalValue = intVar("Total value for capacity $W (unbounded)", 0, unbounded)
var totalWeight = intVar("Total weight taken", 0, W)
knapsack(counts, totalWeight, totalValue, weights, values).post()
setObjective(MAXIMIZE, totalValue)
while (solver.solve()) {
found = true
println "$totalValue, $totalWeight, $counts"
}
}
if (!found) println 'No solution'</code></pre>
</div>
</div>
<div class="paragraph">
<p>Which when run has this output:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>Total value for capacity 10 (unbounded) = 30, Total weight taken = 10, [count0 = 0, count1 = 2, count2 = 2, count3 = 0, count4 = 0]
Total value for capacity 10 (unbounded) = 31, Total weight taken = 10, [count0 = 1, count1 = 0, count2 = 3, count3 = 0, count4 = 0]</pre>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_using_ortools">Using OrTools</h2>
<div class="sectionbody">
<div class="paragraph">
<p>Other libraries also have built-in solvers for knapsack.
Here is another implementation using the OrTools library:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">Loader.loadNativeLibraries()
var solver = new KnapsackSolver(KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "knapsack")
long[] values = [1, 5, 10, 15, 17]
long[][] weights = [[1, 2, 3, 5, 6]]
long[] capacities = [10]
solver.init(values, weights, capacities)
long computedValue = solver.solve()
println "Total value for capacity ${capacities[0]} = " + computedValue
var packedItems = []
var packedWeights = []
int totalWeight = 0
values.indices.each { i -&gt;
if (solver.bestSolutionContains(i)) {
packedItems &lt;&lt; i
packedWeights &lt;&lt; weights[0][i]
totalWeight += weights[0][i]
}
}
println "Actual weight: $totalWeight"
println "Gems taken: $packedItems"
println "Gem weights: $packedWeights"</code></pre>
</div>
</div>
<div class="paragraph">
<p>Which when run has this output:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>Total value for capacity 10 = 30
Actual weight: 10
Gems taken: [1, 2, 3]
Gem weights: [2, 3, 5]</pre>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_using_jenetics">Using Jenetics</h2>
<div class="sectionbody">
<div class="paragraph">
<p>We can also use Genetic Algorithms to find a solution.
When creating solutions based on genetic algorithms,
a series of steps take place which mimic evolution
in nature. We typically start with some random guesses,
which we regard as the first generation of children.
We have functions to test the fitness of individuals,
processes to select a new generation of children based
on the current generation, steps for mutation and so forth.</p>
</div>
<div class="paragraph">
<p>We&#8217;ll start by creating a record to track our weights and values:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">record Item(int weight, int value) implements Serializable {}</code></pre>
</div>
</div>
<div class="paragraph">
<p>We&#8217;ll create a <code>Knapsack</code> class to keep track of state
and provide our fitness function:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">class Knapsack implements Problem&lt;ISeq&lt;Item&gt;, BitGene, Integer&gt; {
private final Codec&lt;ISeq&lt;Item&gt;, BitGene&gt; codec
private final double knapsackSize
Knapsack(ISeq&lt;Item&gt; items, int knapsackSize) {
codec = Codecs.ofSubSet(items)
this.knapsackSize = knapsackSize
}
@Override
Function&lt;ISeq&lt;Item&gt;, Integer&gt; fitness() {
(items) -&gt; {
var sum = items.inject(new Item(0, 0)) { acc, next -&gt;
new Item(acc.weight + next.weight, acc.value + next.value)
}
sum.weight &lt;= knapsackSize ? sum.value : 0
}
}
@Override
Codec&lt;ISeq&lt;Item&gt;, BitGene&gt; codec() { codec }
}</code></pre>
</div>
</div>
<div class="paragraph">
<p>We create our genetic algorithm engine and
configure it work out how the next generation
will be selected, and what mutations, if any,
might be used to provide random alterations.</p>
</div>
<div class="paragraph">
<p>We&#8217;ll also create a <code>log</code> function to output some
information as our various generations are being produced.</p>
</div>
<div class="paragraph">
<p>Here is the script:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int W = 10
int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
var items = [weights, values].transpose().collect { w, v -&gt; new Item(w, v) }
var iSeq = items.stream().collect(ISeq.toISeq())
var knapsack = new Knapsack(iSeq, W)
var engine = Engine.builder(knapsack)
.populationSize(8)
.survivorsSelector(new TournamentSelector&lt;&gt;(3))
.offspringSelector(new RouletteWheelSelector&lt;&gt;())
.alterers(
new Mutator&lt;&gt;(0.1),
new SinglePointCrossover&lt;&gt;(0.2),
new MultiPointCrossover&lt;&gt;(0.1))
.build()
var log = { EvolutionResult er -&gt;
var avg = er.population().average{ it.fitness() }
var best = er.bestFitness()
printf "avg = %5.2f, best = %d%n", avg, best
}
var best = engine.stream()
.limit(bySteadyFitness(8))
.limit(30)
.peek(log)
.collect(toBestPhenotype())
println best</code></pre>
</div>
</div>
<div class="paragraph">
<p>Which when run produces this output:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>avg = 18.88, best = 23
avg = 21.00, best = 25
avg = 22.00, best = 25
avg = 22.63, best = 25
avg = 25.63, best = 30
avg = 27.50, best = 30
avg = 27.63, best = 30
avg = 24.38, best = 30
avg = 22.50, best = 30
avg = 26.25, best = 30
avg = 30.00, best = 30
avg = 30.00, best = 30
[00001110] -&gt; 30</pre>
</div>
</div>
<div class="paragraph">
<p>Since it is random, subsequent runs may produce different results:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>avg = 16.75, best = 27
avg = 17.13, best = 23
avg = 18.00, best = 23
avg = 21.38, best = 27
avg = 24.00, best = 27
avg = 24.88, best = 27
avg = 22.50, best = 27
avg = 26.88, best = 27
[00010100] -&gt; 27</pre>
</div>
</div>
<div class="paragraph">
<p>As we can see here, we aren&#8217;t guaranteed to get the optimal
solution with all genetic algorithm problems.</p>
</div>
<div class="paragraph">
<p>What we should notice is that while the process involves
various random aspects, and we might sometimes actually kill off
best individuals, if we have configured
our algorithm correctly, we should see that the average
and best fitness values go up over time.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_using_greedy_selection">Using Greedy selection</h2>
<div class="sectionbody">
<div class="paragraph">
<p>The final example we will look at is the "optimal" or "greedy"
solution. Here we take the items in order of best value/weight.
If we allowed a fractional value greater than 1, we&#8217;d
just use the first item in this sorted list, but here we&#8217;ll
have a maximum of 1 for any item.</p>
</div>
<div class="paragraph">
<p>For this problem, instead of gems, which might indeed be hard to split
(or at least split and not devalue significantly),
you might instead think of exotic spices, or some other
valuable which can be readily divided.</p>
</div>
<div class="paragraph">
<p>Here is the code:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="prettyprint highlight"><code data-lang="groovy">int[] values = [1, 5, 10, 15, 17] // Gem values
int[] weights = [1, 2, 3, 5, 6] // Weights
var ratios = values.indices.collect { values[it] / weights[it] }.withIndex().sort { -it[0] }
int W = 10
Map&lt;Integer, BigDecimal&gt; taken = [:]
var remaining = W
while (remaining &amp;&amp; ratios) {
var next = ratios.head()
var index = next[1]
if (remaining &gt;= weights[index]) {
taken[index] = 1
remaining -= weights[index]
} else {
taken[index] = remaining / weights[index]
break
}
ratios = ratios.tail()
}
var total = taken.collect{ index, qty -&gt; values[index] * qty }.sum()
println taken
printf 'Total value for capacity %d (with fractions) = %6.3f%n', W, total</code></pre>
</div>
</div>
<div class="paragraph">
<p>Which when run has this output:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>[2:1, 3:1, 4:0.3333333333]
Total value for capacity 10 (with fractions) = 30.667</pre>
</div>
</div>
<div class="paragraph">
<p>It is not unexpected that we can obtain a value greater than 30
when allowing fractional amounts of the valuables.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_further_information">Further information</h2>
<div class="sectionbody">
<div class="ulist">
<ul>
<li>
<p><a href="https://www.youtube.com/watch?v=xCbYmUPvc2Q">The 0/1 Knapsack Problem (Demystifying Dynamic Programming)</a></p>
</li>
<li>
<p><a href="https://www.youtube.com/watch?v=MacVqujSXWE">The Knapsack Problem &amp; Genetic Algorithms - Computerphile</a></p>
</li>
<li>
<p><a href="https://www.youtube.com/watch?v=cJ21moQpofY">0/1 Knapsack problem | Dynamic Programming</a></p>
</li>
<li>
<p><a href="https://www.youtube.com/watch?v=zRza99HPvkQ">0/1 Knapsack Problem (Program) - Dynamic Programming</a></p>
</li>
<li>
<p><a href="https://www.youtube.com/watch?v=nLmhmB6NzcM">0/1 Knapsack - Two Methods - Dynamic Programming</a></p>
</li>
<li>
<p><a href="https://www.youtube.com/watch?v=oTTzNMHM05I">Knapsack Problem - Greedy Method</a></p>
</li>
<li>
<p><a href="https://www.baeldung.com/java-knapsack">Baeldung: Knapsack Problem Implementation in Java</a></p>
</li>
<li>
<p><a href="https://www.hindawi.com/journals/mpe/2023/1742922/">Solving the 0/1 Knapsack Problem Using Metaheuristic and Neural Networks for the Virtual Machine Placement Process in Cloud Computing Environment</a></p>
</li>
<li>
<p>Choco Solver: <a href="https://choco-solver.org/">home page</a>,
<a href="https://choco-solver.org/tutos/other-examples/the_knapsack_problem/">a different knapsack example</a></p>
</li>
<li>
<p>OR-Tools: <a href="https://developers.google.com/optimization">home page</a>,
<a href="https://developers.google.com/optimization/pack/knapsack">a different knapsack example</a></p>
</li>
<li>
<p><a href="https://www.boardinfinity.com/blog/branch-and-bound-algorithm/">Branch And Bound Algorithm: Explained</a></p>
</li>
<li>
<p><a href="https://github.com/paulk-asert/groovy-knapsack">Example source code</a></p>
</li>
</ul>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_conclusion">Conclusion</h2>
<div class="sectionbody">
<div class="paragraph">
<p>We have seen how to solve the knapsack problem in Groovy
using several approaches. In the references, there are even
more exotic algorithms which can be used to solve the knapsack problem.</p>
</div>
</div>
</div></div></div></div></div><footer id='footer'>
<div class='row'>
<div class='colset-3-footer'>
<div class='col-1'>
<h1>Groovy</h1><ul>
<li><a href='https://groovy-lang.org/learn.html'>Learn</a></li><li><a href='https://groovy-lang.org/documentation.html'>Documentation</a></li><li><a href='/download.html'>Download</a></li><li><a href='https://groovy-lang.org/support.html'>Support</a></li><li><a href='/'>Contribute</a></li><li><a href='https://groovy-lang.org/ecosystem.html'>Ecosystem</a></li><li><a href='/blog'>Blog posts</a></li><li><a href='https://groovy.apache.org/events.html'></a></li>
</ul>
</div><div class='col-2'>
<h1>About</h1><ul>
<li><a href='https://github.com/apache/groovy'>Source code</a></li><li><a href='https://groovy-lang.org/security.html'>Security</a></li><li><a href='https://groovy-lang.org/learn.html#books'>Books</a></li><li><a href='https://groovy-lang.org/thanks.html'>Thanks</a></li><li><a href='http://www.apache.org/foundation/sponsorship.html'>Sponsorship</a></li><li><a href='https://groovy-lang.org/faq.html'>FAQ</a></li><li><a href='https://groovy-lang.org/search.html'>Search</a></li>
</ul>
</div><div class='col-3'>
<h1>Socialize</h1><ul>
<li><a href='https://groovy-lang.org/mailing-lists.html'>Discuss on the mailing-list</a></li><li><a href='https://twitter.com/ApacheGroovy'>Groovy on Twitter</a></li><li><a href='https://groovy-lang.org/events.html'>Events and conferences</a></li><li><a href='https://github.com/apache/groovy'>Source code on GitHub</a></li><li><a href='https://groovy-lang.org/reporting-issues.html'>Report issues in Jira</a></li><li><a href='http://stackoverflow.com/questions/tagged/groovy'>Stack Overflow questions</a></li><li><a href='http://groovycommunity.com/'>Slack Community</a></li>
</ul>
</div><div class='col-right'>
<p>
The Groovy programming language is supported by the <a href='http://www.apache.org'>Apache Software Foundation</a> and the Groovy community.
</p><div text-align='right'>
<img src='../img/asf_logo.png' title='The Apache Software Foundation' alt='The Apache Software Foundation' style='width:60%'/>
</div><p>Apache&reg; and the Apache feather logo are either registered trademarks or trademarks of The Apache Software Foundation.</p>
</div>
</div><div class='clearfix'>&copy; 2003-2024 the Apache Groovy project &mdash; Groovy is Open Source: <a href='http://www.apache.org/licenses/LICENSE-2.0.html' alt='Apache 2 License'>license</a>, <a href='https://privacy.apache.org/policies/privacy-policy-public.html'>privacy policy</a>.</div>
</div>
</footer></div>
</div>
</div>
</div>
</div><script src='../js/vendor/jquery-1.10.2.min.js' defer></script><script src='../js/vendor/classie.js' defer></script><script src='../js/vendor/bootstrap.js' defer></script><script src='../js/vendor/sidebarEffects.js' defer></script><script src='../js/vendor/modernizr-2.6.2.min.js' defer></script><script src='../js/plugins.js' defer></script><script src='https://cdnjs.cloudflare.com/ajax/libs/prettify/r298/prettify.min.js'></script><script>document.addEventListener('DOMContentLoaded',prettyPrint)</script><script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-257558-10', 'auto');
ga('send', 'pageview');
</script>
</body></html>