Algorithms - Revision history

WikiSysop: /* Exercises */

2025-08-05T09:52:29Z

Exercises

← Older revision		Revision as of 11:52, 5 August 2025
Line 19:		Line 19:
	The size of your knapsack is 342. You can start with selecting among the first 20 items on the list for testing. The problem grows exponentially larger with the number of items, so do be careful how many you select from.		The size of your knapsack is 342. You can start with selecting among the first 20 items on the list for testing. The problem grows exponentially larger with the number of items, so do be careful how many you select from.

	The exercise can be done on your laptop. ~~Computerome~~ is not needed, but can be used.<br>		The exercise can be done on your laptop. Pupil1 is not needed, but can be used.<br>
	Using the first 20 items on the list the result is<br>		Using the first 20 items on the list the result is<br>
	Items: 13<br>		Items: 13<br>

WikiSysop: /* Material for the lesson */

2024-06-17T09:27:07Z

Material for the lesson

← Older revision		Revision as of 11:27, 17 June 2024
Line 7:		Line 7:
	Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=f0af095e-eb23-44b3-9221-af2701235802 Dr Jones on Branch & Bound]<br>		Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=f0af095e-eb23-44b3-9221-af2701235802 Dr Jones on Branch & Bound]<br>
	Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=8ef014eb-aa14-45a1-8588-af2701232e21 MaxAlign example]<br>		Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=8ef014eb-aa14-45a1-8588-af2701232e21 MaxAlign example]<br>
	Powerpoint: [https://teaching.healthtech.dtu.dk/material/22112/~~HPCLife05~~-Algorithms.ppt Algorithms]<br>		Powerpoint: [https://teaching.healthtech.dtu.dk/material/22112/22112_08-Algorithms.ppt Algorithms]<br>
	Example: [https://teaching.healthtech.dtu.dk/material/22112/~~HPCLife05~~-MaxAlign.ppt MaxAlign]<br>		Example: [https://teaching.healthtech.dtu.dk/material/22112/22112_08-MaxAlign.ppt MaxAlign]<br>
	Web service: [http://www.cbs.dtu.dk/services/MaxAlign MaxAlign web service]<br>		Web service: [http://www.cbs.dtu.dk/services/MaxAlign MaxAlign web service]<br>
	PDF: [https://teaching.healthtech.dtu.dk/material/22112/~~HPCLife05~~-BranchBound.pdf Branch and Bound]<br>		PDF: [https://teaching.healthtech.dtu.dk/material/22112/22112_08-BranchBound.pdf Branch and Bound]<br>
	Example: [http://optlab-server.sce.carleton.ca/POAnimations2007/BranchAndBound.html B&B example]<br>		Example: [http://optlab-server.sce.carleton.ca/POAnimations2007/BranchAndBound.html B&B example]<br>
	Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=92087938-aa47-4dbf-8ee3-af2701231587 What is expected in exercises]		Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=92087938-aa47-4dbf-8ee3-af2701231587 What is expected in exercises]

WikiSysop: Created page with "{| width=500 style="float:right; margin-left: 10px; margin-top: -56px;" |Previous: What affects performance |Next: Parallel programming |} == Material for the lesson == Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=a7649b3f-c5bd-4326-be50-af270123913f Algorithms are good]
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=f0af095e-eb23-44b3-9221-af2701235802 Dr Jones on Branch & Bound]
Video: [https://panopto.dtu.dk/Panopto/Pages/V..."

2024-03-06T10:54:36Z

Created page with "{| width=500 style="float:right; margin-left: 10px; margin-top: -56px;" |Previous: What affects performance |Next: Parallel programming |} == Material for the lesson == Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=a7649b3f-c5bd-4326-be50-af270123913f Algorithms are good] Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=f0af095e-eb23-44b3-9221-af2701235802 Dr Jones on Branch & Bound] Video: [https://panopto.dtu.dk/Panopto/Pages/V..."

New page

{| width=500 style="float:right; margin-left: 10px; margin-top: -56px;"
|Previous: [[What affects performance]]
|Next: [[Parallel programming]]
|}
== Material for the lesson ==
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=a7649b3f-c5bd-4326-be50-af270123913f Algorithms are good] 
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=f0af095e-eb23-44b3-9221-af2701235802 Dr Jones on Branch & Bound] 
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=8ef014eb-aa14-45a1-8588-af2701232e21 MaxAlign example] 
Powerpoint: [https://teaching.healthtech.dtu.dk/material/22112/HPCLife05-Algorithms.ppt Algorithms] 
Example: [https://teaching.healthtech.dtu.dk/material/22112/HPCLife05-MaxAlign.ppt MaxAlign] 
Web service: [http://www.cbs.dtu.dk/services/MaxAlign MaxAlign web service] 
PDF: [https://teaching.healthtech.dtu.dk/material/22112/HPCLife05-BranchBound.pdf Branch and Bound] 
Example: [http://optlab-server.sce.carleton.ca/POAnimations2007/BranchAndBound.html B&B example] 
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=92087938-aa47-4dbf-8ee3-af2701231587 What is expected in exercises]

== Exercises ==
In the file '''knapsack.lst''' you find 100 different items with varying size and value. 
Make a program that selects the subset of items that can be in your knapsack and has the biggest value. This is a combinatorial maximization problem. 
The size of your knapsack is 342. You can start with selecting among the first 20 items on the list for testing. The problem grows exponentially larger with the number of items, so do be careful how many you select from.

The exercise can be done on your laptop. Computerome is not needed, but can be used. 
Using the first 20 items on the list the result is 
Items: 13 
Combined size: 341.7 
Combined value: 1704.8 

This is known as "The Knapsack Problem" and is typically solved using the Branch and Bound paradigm. 
https://en.wikipedia.org/wiki/Knapsack_problem

Challenge: Done right, this can be solved for the entire list in less than 1/10 second, done wrong you can wait years for the program to finish.

To help you understand the core of the "branch" part of the algorithm that goes through the search tree, run this python code.
It is here for your understanding, not for performance. Once you understand the principle, you can adapt the code to your problem.
<pre>
#!/usr/bin/env python3

maxsize = 100
problem = 'XXXX'
bestproblem = ''
bestvalue = 0
stack = [problem]

while len(stack) > 0:
problem = stack.pop()
# Calculate bound/estimate and constraint of choices
# This is not done for you - calculate your own
estimate = 0
size = 45
# if bound/estimate is worse than any previous found solution, discard
if estimate < bestvalue:
continue
# Are constraints exceeded, discard
if size > maxsize:
continue
# Still not solved, then split the problem
if 'X' in problem:
nextx = problem.find('X')
stack.append(problem[:nextx] + '1' + problem[nextx+1:])
stack.append(problem[:nextx] + '0' + problem[nextx+1:])
# Solved, is the better than any solution so far?
elif estimate > bestvalue:
bestvalue = estimate
bestproblem = problem
# What is going on with the stack???
print(stack)
</pre>