Google Git
Sign in
apache / groovy-dev-site / 9b28127a1faec4352f9bace50837478e6ccee744 / . / blog / groovy-knapsack.html
blob: 5d2152d93602ad375dd3a8b69c977bacbaebc2c3 [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_recursion' class='anchor-link'>Brute force recursion</a></li><li><a href='#_using_dynamic_programming' class='anchor-link'>Using Dynamic Programming</a></li><li><a href='#_using_branch_and_bound' class='anchor-link'>Using Branch and Bound</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">Number</th>
<th class="tableblock halign-left valign-top">Weight</th>
<th class="tableblock halign-left valign-top">Value</th>
</tr>
</thead>
<tbody>
<tr>
<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>
<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">2</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">3</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">4</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">5</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.</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_recursion">Brute force recursion</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 indexCombos = weights.indices.collect{ [null, it] }.combinations()*.findResults()
var validWeight = indexCombos.findAll{ weights[it].sum() &lt;= W }
var best = validWeight.max{ values[it].sum() }
println "Total value for capacity $W = ${values[best].sum()}"
println "Gems taken: $best"
println "Gem weights: ${weights[best]}"</code></pre>
</div>
</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. Let&#8217;s instead, consider a recursive solution
which lets us opt out earlier for cases which are over the valid knapsack weight:</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>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>We now have some possibilities for optimisation. One quick win is to
memoize (cache) the results of calling the <code>knapsack</code> method.
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_dynamic_programming">Using Dynamic Programming</h2>
<div class="sectionbody">
<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="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="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_branch_and_bound">Using Branch and Bound</h2>
<div class="sectionbody">
<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="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="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
}
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 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_constraint_programming">Using Constraint Programming</h2>
<div class="sectionbody">
<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="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="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="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="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="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="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="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="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="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="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>
</div>
<div class="sect1">
<h2 id="_using_greedy_selection">Using Greedy selection</h2>
<div class="sectionbody">
<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="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>
</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><a href="https://choco-solver.org/">Choco home page</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.</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>