from random import sample


class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight


class HillClimbingRucsac:
    def __init__(self, path):
        self.no_items = -1
        self.max_weight = -1
        self.items = []
        self.solution = []
        self.current_weight = 0
        self.current_value = 0
        self.read_data(path)

    def read_data(self, path):
        file = open(path, "r")
        params = []
        for line in file:
            words = line.replace("\n", "").split(" ")
            params.append(int(words[0]))
            params.append(int(words[1]))
        file.close()
        self.no_items = params[0]
        self.max_weight = params[1]

        for i in range(2, self.no_items, 2):
            self.items.append(Item(params[i], params[i + 1]))

        # initial solution
        self.solution = [0 for i in range(0, self.no_items)]

    def run_hill_climbing(self):
        free_positions = []
        for i in range(0, self.no_items):
            if self.solution[i] == 0:
                free_positions.append(i)

        while free_positions:
            position = sample(free_positions, 1)[0]
            free_positions.remove(position)
            new_sol = self.solution[:]
            new_sol[position] = 1
            value, weight = self.evaluate(new_sol)
            if value > self.current_value:
                self.current_value = value
                self.current_weight = weight
                self.solution = new_sol[:]
        print(self.current_value, self.current_weight, self.solution)

    def evaluate(self, new_sol):
        return -1,-1