Discrete Optimization: Assignments: Knapsack

Discrete
Optimization
Assignments: Knapsack
The Knapsack Problem
2
The Knapsack Problem
‣ n Items#
‣ Value Vi#
‣ Weight Wi#
‣ Xi take item i
X
maximize: v i xi
i21...n
subject to: X
w i xi  K
i21...n
xi 2 {0, 1} (i 2 1 . . . n)
3
I/O Format
X
maximize: v i xi
i21...n
subject to: X
w i xi  K
i21...n
xi 2 {0, 1} (i 2 1 . . . n)
Input
n K Output
v_1 w_1
obj opt
v_2 w_2
x_1 x_2 x_3 ... x_n
...
v_n w_n
4
An Example
X
maximize: v i xi
i21...n
subject to: X
w i xi  K
i21...n
xi 2 {0, 1} (i 2 1 . . . n)
Input
4 11 Output
8 4
19 0
10 5
0 0 1 1
15 8
4 3
5
Implementing Your solver.py
import os
#
def solveIt(inputData):
### Modify this code to run your optimization algorithm
lines = inputData.split('\n')
#
...
#
outputData = str(value)+' '+str(0)+'\n'
outputData += ' '.join(map(str,taken))
return outputData
Input
4 11 Output
8 4
19 0
10 5
0 0 1 1
15 8
4 3
6
Implementing an External Solver
def solveIt(inputData):
tmpFileName = 'tmp.data' solverJava.py
tmpFile = open(tmpFileName,'w')
tmpFile.write(inputData)
...
### Runs the command: java Solver -file=tmp.data
process = Popen(['java','Solver','-file='+tmpFileName], stdout=PIPE)
(stdout, stderr) = process.communicate()
...
return stdout.strip()
class Solver {
public static void main(String[] args) { Solver.java
new Solver().run(args);
}
public void run(String[] args) {
...
System.out.println(value+" 0");
for(int i=0; i < items; i++){
System.out.print(taken[i]+" ");
}
System.out.println("");
}
}
7
Testing Your Solver
> python solver.py ./data/ks_4_0
18 0
1 1 0 0
#
>
8
Grading Your Solver
> python submit.pyc
==
== Knapsack Solution Submission
==
Login (Email address):
Submission Password (from the programming assignments page.
This is NOT your own account's password):
#
== Connecting to Coursera ...
Hello! These are the assignment parts that you can submit:
1) Knapsack Problem 1
0) All
Please enter which part(s) you want to submit (0-6):
9
Grading Your Solver
== Connecting to Coursera ...
Hello! These are the assignment parts that you can submit:
0) All
Please enter which part(s) you want to submit (0-6):
Please enter which part(s) you want to submit (0-6): 3
Please enter which part(s) you want to submit (0-6): 0
Please enter which part(s) you want to submit (0-6): 4, 6
10
Assignment Tips
‣ Dynamic Program#
– How much space do you need?#
#
‣ Branch and Bound#

– What is the fastest way to calculate the
relaxation value?
12
Have Fun!
13
Citations
Stone Foundation Tablet with Inscription of Gudea - 41221 (http://commons.wikimedia.org/wiki/File:Sumerian _-
_Stone_Foundation_Tablet_with_Inscription_of_Gudea_-_Walters_41221_-_View_A.jpg). Artist Unknown. Walters Art Museum [Public domain, CC-BY-SA-3.0
(http://creativecommons.org/licenses/by-sa/3.0 )], via Wikimedia Commons #
#
Stone Foundation Tablet with Inscription of Gudea - 41220 (http://commons.wikimedia.org/wiki/File:Sumerian_-_
Stone_Foundation_Tablet_with_an_Inscription_of_Gudea_-_Walters_41220_-_View_A.jpg). Artist Unknown. Walters Art Museum [Public domain, CC-BY-SA-3.0
(http://creativecommons.org/licenses/by-sa/3.0) via Wikimedia Commons #
#
Buddha at the Moment of Victory (http://commons.wikimedia.org/wiki/File:Thai_-_Buddha_at_the_Moment_of_Victory_-_Walters_542775.jpg ). Artist Unknown.
Walters Art Museum [Public domain, CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0 )], via Wikimedia Commons #
#
Hoxne Hoard two gold bracelets (http://commons.wikimedia.org/wiki/File:Hoxne_Hoard_two_gold_bracelets_side.JPG) by Fæ (http://commons.wikimedia.org/
wiki/User:F%C3%A6) [CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons #
#
Ring with the engraved portrait of Ptolemy VI Philometor (http://commons.wikimedia.org/wiki/File:Ring_with_engraved_portrait_of_ Ptolemy_VI_Philometor_(3rd
%E2%80%932nd_century_BCE)_-_2009.jpg<http://commons.wikimedia.org/wiki/File:Ring_with_engraved_
portrait_of_Ptolemy_VI_Philometor_(3rd-2nd_century_BCE)_-_2009.jpg>) By Unknown. (Photographed by PHGCOM in 2009.) [Public domain], via Wikimedia
Commons #
#
Calice du sacre Tau (http://commons.wikimedia.org/wiki/File:Calice_du_sacre_Tau.jpg) By Vassil (http://commons.wikimedia.org/wiki/User:Vassil) (Own work)
[Public domain], via Wikimedia Commons #
14
Citations
the mask of agamemnon (http://www.flickr.com/photos/rosemania/5705122218/) by Xuan Che (http://www.flickr.com/people/rosemania/) CC BY-2.0 (http://
creativecommons.org/licenses/by/2.0/deed.en) #
#
Terracotta Warrior (http://www.flickr.com/photos/59627558@N00/4677378806/) by fixermark (http://www.flickr.com/photos/59627558@N00/) CC BY 2.0 (http://
creativecommons.org/licenses/by/2.0/deed.en)#
15

Discrete Optimization: Assignments: Knapsack

Uploaded by

Copyright:

Available Formats

Discrete Optimization: Assignments: Knapsack

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete Optimization: Assignments: Knapsack

Uploaded by

Copyright:

Available Formats

Discrete

Please enter which part(s) you want to submit (0-6): 3

Please enter which part(s) you want to submit (0-6): 0

Please enter which part(s) you want to submit (0-6): 4, 6

‣ Branch and Bound#

You might also like