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]

        i = 2
        while i < len(params):
            self.items.append(Item(params[i], params[i + 1]))
            i += 2

        # 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):
        w = 0
        v = 0
        for i in range(0, len(new_sol)):
            if new_sol[i] == 1:
                w += self.items[i].weight
                v += self.items[i].value

        if w > self.max_weight:
            return -1, -1
        return v, w