nodes: 0, module; 1, function_definition; 2, function_name:knapsack_greedy; 3, parameters; 4, block; 5, identifier:items; 6, identifier:maxweight; 7, expression_statement; 8, expression_statement; 9, expression_statement; 10, expression_statement; 11, for_statement; 12, return_statement; 13, comment:r"""
      non-optimal greedy version of knapsack algorithm
      does not sort input. Sort the input by largest value
      first if desired.
  
      Args:
          `items` (tuple): is a sequence of tuples `(value, weight, id_)`, where `value`
              is a scalar and `weight` is a non-negative integer, and `id_` is an
              item identifier.
  
          `maxweight` (scalar):  is a non-negative integer.
  
      CommandLine:
          python -m utool.util_alg --exec-knapsack_greedy
  
      Example:
          >>> # ENABLE_DOCTEST
          >>> from utool.util_alg import *  # NOQA
          >>> items = [(4, 12, 0), (2, 1, 1), (6, 4, 2), (1, 1, 3), (2, 2, 4)]
          >>> maxweight = 15
          >>> total_value, items_subset = knapsack_greedy(items, maxweight)
          >>> result =  'total_value = %r\n' % (total_value,)
          >>> result += 'items_subset = %r' % (items_subset,)
          >>> print(result)
          total_value = 7
          items_subset = [(4, 12, 0), (2, 1, 1), (1, 1, 3)]
      """; 14, assignment; 15, assignment; 16, assignment; 17, identifier:item; 18, identifier:items; 19, block; 20, expression_list; 21, identifier:items_subset; 22, list; 23, identifier:total_weight; 24, integer:0; 25, identifier:total_value; 26, integer:0; 27, expression_statement; 28, if_statement; 29, identifier:total_value; 30, identifier:items_subset; 31, assignment; 32, comparison_operator:total_weight + weight > maxweight; 33, block; 34, else_clause; 35, pattern_list; 36, subscript; 37, binary_operator:total_weight + weight; 38, identifier:maxweight; 39, continue_statement; 40, block; 41, identifier:value; 42, identifier:weight; 43, identifier:item; 44, slice; 45, identifier:total_weight; 46, identifier:weight; 47, expression_statement; 48, expression_statement; 49, expression_statement; 50, integer:0; 51, integer:2; 52, call; 53, augmented_assignment; 54, augmented_assignment; 55, attribute; 56, argument_list; 57, identifier:total_weight; 58, identifier:weight; 59, identifier:total_value; 60, identifier:value; 61, identifier:items_subset; 62, identifier:append; 63, identifier:item
code: def knapsack_greedy(items, maxweight):
      r"""
      non-optimal greedy version of knapsack algorithm
      does not sort input. Sort the input by largest value
      first if desired.
  
      Args:
          `items` (tuple): is a sequence of tuples `(value, weight, id_)`, where `value`
              is a scalar and `weight` is a non-negative integer, and `id_` is an
              item identifier.
  
          `maxweight` (scalar):  is a non-negative integer.
  
      CommandLine:
          python -m utool.util_alg --exec-knapsack_greedy
  
      Example:
          >>> # ENABLE_DOCTEST
          >>> from utool.util_alg import *  # NOQA
          >>> items = [(4, 12, 0), (2, 1, 1), (6, 4, 2), (1, 1, 3), (2, 2, 4)]
          >>> maxweight = 15
          >>> total_value, items_subset = knapsack_greedy(items, maxweight)
          >>> result =  'total_value = %r\n' % (total_value,)
          >>> result += 'items_subset = %r' % (items_subset,)
          >>> print(result)
          total_value = 7
          items_subset = [(4, 12, 0), (2, 1, 1), (1, 1, 3)]
      """
      items_subset = []
      total_weight = 0
      total_value = 0
      for item in items:
          value, weight = item[0:2]
          if total_weight + weight > maxweight:
              continue
          else:
              items_subset.append(item)
              total_weight += weight
              total_value += value
      return total_value, items_subset