knapscak and graph optimization problems function is roughly ( log )where is the length of the list to be sorted therefore the running time of greedy is ( log nan optimal solution to the / knapsack problem suppose we decide that an approximation is not good enoughi we want the best possible solution to this problem such solution is called optimalnot surprising since we are solving an optimization problem as it happensthis is an instance of classic optimization problemcalled the / knapsack problem the / knapsack problem can be formalized as follows each item is represented by pair the knapsack can accommodate items with total weight of no more than vectoriof length nrepresents the set of available items each element of the vector is an item vectorvof length nis used to indicate whether or not each item is taken by the burglar if [ item [iis taken if [ item [iis not taken find that maximizes " # [ ] [ivalue subject to the constraint that # $ [ ] [iweight let' see what happens if we try to implement this formulation of the problem in straightforward way enumerate all possible combinations of items that is to saygenerate all subsets of the set of items this is called the power setand was discussed in remove all of the combinations whose weight exceeds the allowed weight from the remaining combinations choose any one whose value is the largest this approach will certainly find an optimal answer howeverif the original set of items is largeit will take very long time to runbecauseas we saw in the number of subsets grows exceedingly quickly with the number of items figure contains straightforward implementation of this brute-force approach to solving the / knapsack problem it uses the classes and functions defined in figure and figure and the function genpowerset defined in figure as we discussed in the time complexity of the sorting algorithmtimsortused in most python implementations is ( log recall that every set is subset of itself and the empty set is subset of every set