knapsack/ChangeLog at main · vaeth/knapsack · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# ChangeLog for knapsack

*knapsack-7.3.1
	Martin Väth <martin at mvath.de>:
	- Use standard boost library name

*knapsack-7.3
	Martin Väth <martin at mvath.de>:
	- Add SPDX-License-Identifier

*knapsack-7.2.1
	Martin Väth <martin at mvath.de>:
	- Cleaner code concerning boost exceptions

*knapsack-7.2
	Martin Väth <martin at mvath.de>:
	- Use std::uintmax_t if available
	- Fix usage of [[noreturn]]
	- Makefile: Use C++-14 when optimizing
	- Makefile: More systematic OPTIMIZE/WARN with clang and/or gcc

*knapsack-7.1
	Martin Väth <martin at mvath.de>:
	- Makefile: add switch CLANG=1
	- testsuite: output time
	- internal: option parsing cleanup

*knapsack-7.0
	Martin Väth <martin at mvath.de>:
	- CLI: Select unbound case (and print a warning) if possible
	- CLI: Omit too heavy items immediately
	- CLI: Add option -q/--quiet to suppress the warnings
	- CLI: Add option -F/--force to suppress the omission/unbound selection
	- Fix zsh completion
	- internal: Avoid SackSet altogether. Use only one static iterator list
	  (in Calc) which is never copied. This way the hash stores less
	  redundant data which saves memory and time. The only redundancy
	  stored in the hash now is the tree structure from the set; avoiding
	  that would increase time for modification from logarithmic to linear.

*knapsack-6.2
	Martin Väth <martin at mvath.de>:
	- internal: Implement SackSet without an iterator list; modification
	  needs now twice the time, but copying is so much faster even for few
	  sacks that this compensates. (For many sacks, copying with iterators
	  would in addition need a logarithmic factor anyway or another
	  constant factor due to using (or maintaining) inverse lookup.)
	  In theory, boost:::multi_index could do the same without the
	  modification overhead, but in practice it turned out to be slower.
	  Also attempts to not maintain a sorted list at all (reasonable only
	  for few sacks due to a logarithmic factor) turned out to be slower
	  even for few sacks.

*knapsack-6.1
	Martin Väth <martin at mvath.de>:
	- CLI: Use long options and improve description and error output
	- CLI: Allow item specification by option (-i)
	- internal: Use boost::program_options
	- internal: lexical_cast instead of manual conversion
	- testsuite: Improve readability by using set -f

*knapsack-6.0
	Martin Väth <martin at mvath.de>:
	- Bugfix: In some corner cases (when bound and unbound items both occur
	  and certain strategies for placing unbound items first fail),
	  knapsack-4.0 and knapsack-5.0 could fail to return all items:
	  The optimal value was calculated correctly, but the returned/output
	  optimal solution might be missing some items.

*knapsack-5.0
	Martin Väth <martin at mvath.de>:
	- knapsack-4.0 made for bound items mistakenly the sack part of the
	  hash index instead of the stored data. This led to correct results,
	  but it could multiply the time and space requirements by the number
	  of used sacks. Now also for bound items the index should be correct.
	- Use boost::unordered_map instead of std::unordered_map so that C++-11
	  is not mandatory and hash functions can be declared "boost" style
	- knapsack-4.0 had an unknown bug which sometimes caused to miss an
	  optimal solution; apparently this was fixed by code rewriting done
	  for the above fixes.
	- testsuite: Some instances are fixed: The solution is better than what
	  "manual" guessing (confirmed by buggy knapsack-4.0) had found.
	  Unfortunately, I do not have access to independent examples, so code
	  or testsuite might still contain undetected bugs...
	- Makefile: Do not force C++-11

*knapsack-4.0
	Martin Väth <martin at mvath.de>:
	- This is practically a complete rewrite, saving only some concepts:
	- Support multiple knapsacks
	- Support mixing bound and unbound items
	- Handle multiplicity of items without re-entering
	- Possibly fix false results in the bound case (the old function used
	  an output logic which might be too simple in some complex situations)
	- CLI supports now integer values (even by default)
	- Complete rework of EAPI and CLI
	- Depend on boost for hashing
	- Since boost is needed anyway, depend also on boost::format
	- Drop dependency on https://github.com/vaeth/osformat

*knapsack-3.0
	Martin Väth <martin at mvath.de>:
	- Use https://github.com/vaeth/osformat for typesafe output:
	- Turn the classes in knapsack_output.h into generic templates
	  (which is possible using the osformat class)
	- Let the CLI use the highest integer/floating precision which is
	  natively supported by the compiler

*knapsack-2.0
	Martin Väth <martin at mvath.de>:
	- Provide libraries as generic templates
	- Provide zsh completion
	- Provide a tiny testsuite
	- Provide a Makefile
	- Add .gitignore and CPPLINT

*knapsack-1.0
	Martin Väth <martin at mvath.de>:
	- Initial implementation within 1-2 hours