<kaggle_start><code># El problema de la mochila (Knapsack problem - KSP) consiste en encontrar, a partir de los objetos disponibles, el conjunto de objetos que quepa en la mochila cuyo valor acumulado sea máximo. Al igual que en el problema anterior, este problema es fácilmente resoluble haciendo una comprobación de todas las posibles combinaciones de objetos y tomando aquella que más valor tenga. Sin embargo, estos métodos basados en la fuerza bruta son imposibles de aplicar cuando la lista de objetos que se pueden introducir en la mochila crece mucho.
# En esta práctica se trabajará el problema de la mochila, teniendo como objetivo alcanzar una solución que permita calcular conjuntos de objetos óptimos a partir de una lista pequeña de objetos. Como en la práctica anterior, y siguiendo este notebook, se tendrá que hacer uso del lenguaje de programación Python para realizar la práctica, rellenando o modificando el código que se indique a lo largo del notebook. **Se debe realizar una implementación programación dinámica con tabulation**.
# En este notebook se han incluido distintos datasets que representan diferentes configuraciones del problema del KSP, con distintas listas de objetos y tamaños de mochila. El código que acompaña a este notebook permite realizar la lectura de estos ficheros para su procesamiento. Existen varios códigos a lo largo del notebook que deben ser completados o modificados para terminar esta practica. Concretamente, se debe realizar las siguientes implementaciones:
# * Algoritmo de programación dinámica con memoization
# NOTA: los códigos implementados por el alumno deben utilizar [funciones lambda](https://www.w3schools.com/python/python_lambda.asp) en la medida de lo posible.
# Adding imports that will be used
import numpy as np  # linear algebra

# The following code takes all files in the given directory and print the paths of the files
import os

for dirname, _, filenames in os.walk("/kaggle/input"):
    for filename in filenames:
        print(os.path.join(dirname, filename))
# Definition of the tuples that will be read from the input files. These tuples of three positions represent the item index, its value and its weight
import sys
import csv

csv.field_size_limit(sys.maxsize)
from collections import namedtuple

Item = namedtuple(
    "Item", ["index", "value", "weight"]
)  # check https://docs.python.org/3/library/collections.html#collections.namedtuple


# This method checks that the solution is a valid solution. It is that the selected list of items does not weight more than the knapsack capacity
def check_solution(capacity, items, taken):
    weight = 0
    value = 0
    for item in items:
        if taken[item.index] == 1:
            weight += item.weight
            value += item.value
    if weight > capacity:
        print(
            "Incorrect solution, the knapsack capacity is exceeded: Capacity = %f, Weight = %f"
            % (capacity, weight)
        )
        return 0
    return value


# El código a continuación debe ser modificado para implementar una solución basada en [**programación dinámica**](https://es.wikipedia.org/wiki/Programaci%C3%B3n_din%C3%A1mica) que utilice en la medida de lo posible funciones lambda
def solve_with_dp_tabulation(items, capacity):
    """Write here your implementation of dynamic programming with tabulation"""
    value = 0
    weight = 0
    taken = [0] * len(items)
    # write here your implementation of dynamic programming
    # prepare the solution in the specified output format
    output_data = str(value) + " " + str(0) + "\n"
    output_data += " ".join(map(str, taken))
    return output_data, check_solution(capacity, items, taken)


# Optativamente, puede implementar programación dinámica con memoization. Recuerde modificar las condiciones de llamada a estas funciones en solve_it
def solve_with_dp_memoization(items, capacity):
    """Write here your implementation of dynamic programming with memoization. This part is optional but will improve your scoring"""
    value = 0
    weight = 0
    taken = [0] * len(items)
    # write here your implementation of dynamic programming
    # prepare the solution in the specified output format
    output_data = str(value) + " " + str(0) + "\n"
    output_data += " ".join(map(str, taken))
    return output_data, check_solution(capacity, items, taken)


# Aquí debe copiar el código implementado en la P2 para que sea invocado cuando la tabla de la programación dinámica se estime muy grande
def solve_with_greedy(items, capacity):
    """Copy here the implementation of greedy you did in P2"""
    pass


# Aquí debe copiar el código implementado del sort de la P2
def sort(items, cmp):
    """Copy here the implementation of sort you did in P2"""
    pass


# This function takes input data that describes a specific problem of TSP and solve it
def solve_it(input_data):
    # parse the input
    lines = input_data.split("\n")
    firstLine = lines[0].split()
    item_count = int(firstLine[0])
    capacity = int(firstLine[1])
    items = []
    for i in range(1, item_count + 1):
        line = lines[i]
        parts = line.split()
        items.append(Item(i - 1, int(parts[0]), int(parts[1])))
    # Modify this code to adapt it to your solution. Currently
    # tabulation is unconditionally invoked, and therefore it
    # will fail with cases requiring a large table.
    # In order to avoid that problem, add here code which helps
    # deciding what approach must be taken (for example, depending
    # on the number of elements of the table), and adjust the
    # conditions of the following if-statement to choose what
    # function must be dynamically invoked: tabulation,
    # memoization or greedy.
    if True:
        return solve_with_dp_tabulation(items, capacity)
    # elif True:
    #    return solve_with_dp_memoization(items, capacity)
    else:
        return solve_with_greedy(items, capacity)


# For each input file, solve_it is called and the result serialized in the ouputs for kaggle and moodle
str_output_kaggle = [["Filename", "Max_value"]]
str_output_moodle = [["Filename", "Max_value", "Solution"]]
for dirname, _, filenames in os.walk("/kaggle/input"):
    for filename in filenames:
        full_name = dirname + "/" + filename
        with open(full_name, "r") as input_data_file:
            input_data = input_data_file.read()
            output, value = solve_it(input_data)
            str_output_kaggle.append([filename, str(value)])
            str_output_moodle.append([filename, str(value), output.split("\n")[1]])
from IPython.display import FileLink


def submission_generation(filename, str_output):
    os.chdir(r"/kaggle/working")
    with open(filename, "w", newline="") as file:
        writer = csv.writer(file)
        for item in str_output:
            writer.writerow(item)
    return FileLink(filename)


submission_generation("NAME_P4_kaggle.csv", str_output_kaggle)
# The file generated by this method must be uploaded in the task of the "campus virtual". The file to upload in the "campus virtual" must be the one related to one submitted to Kaggle. That is, both submitted files must be generated in the same run
submission_generation("NAME_P4_moodle.csv", str_output_moodle)
<|endoftext|>
[{"Id": 45449554, "ScriptId": 12486770, "ParentScriptVersionId": NaN, "ScriptLanguageId": 9, "AuthorUserId": 1743598, "CreationDate": "10/25/2020 09:27:07", "VersionNumber": 1.0, "Title": "Practica 4 AP KS 2020", "EvaluationDate": "10/25/2020", "IsChange": false, "TotalLines": 148.0, "LinesInsertedFromPrevious": 0.0, "LinesChangedFromPrevious": 0.0, "LinesUnchangedFromPrevious": 148.0, "LinesInsertedFromFork": 0.0, "LinesDeletedFromFork": 0.0, "LinesChangedFromFork": 0.0, "LinesUnchangedFromFork": 148.0, "TotalVotes": 0}]
# El problema de la mochila (Knapsack problem - KSP) consiste en encontrar, a partir de los objetos disponibles, el conjunto de objetos que quepa en la mochila cuyo valor acumulado sea máximo. Al igual que en el problema anterior, este problema es fácilmente resoluble haciendo una comprobación de todas las posibles combinaciones de objetos y tomando aquella que más valor tenga. Sin embargo, estos métodos basados en la fuerza bruta son imposibles de aplicar cuando la lista de objetos que se pueden introducir en la mochila crece mucho.
# En esta práctica se trabajará el problema de la mochila, teniendo como objetivo alcanzar una solución que permita calcular conjuntos de objetos óptimos a partir de una lista pequeña de objetos. Como en la práctica anterior, y siguiendo este notebook, se tendrá que hacer uso del lenguaje de programación Python para realizar la práctica, rellenando o modificando el código que se indique a lo largo del notebook. **Se debe realizar una implementación programación dinámica con tabulation**.
# En este notebook se han incluido distintos datasets que representan diferentes configuraciones del problema del KSP, con distintas listas de objetos y tamaños de mochila. El código que acompaña a este notebook permite realizar la lectura de estos ficheros para su procesamiento. Existen varios códigos a lo largo del notebook que deben ser completados o modificados para terminar esta practica. Concretamente, se debe realizar las siguientes implementaciones:
# * Algoritmo de programación dinámica con memoization
# NOTA: los códigos implementados por el alumno deben utilizar [funciones lambda](https://www.w3schools.com/python/python_lambda.asp) en la medida de lo posible.
# Adding imports that will be used
import numpy as np  # linear algebra

# The following code takes all files in the given directory and print the paths of the files
import os

for dirname, _, filenames in os.walk("/kaggle/input"):
    for filename in filenames:
        print(os.path.join(dirname, filename))
# Definition of the tuples that will be read from the input files. These tuples of three positions represent the item index, its value and its weight
import sys
import csv

csv.field_size_limit(sys.maxsize)
from collections import namedtuple

Item = namedtuple(
    "Item", ["index", "value", "weight"]
)  # check https://docs.python.org/3/library/collections.html#collections.namedtuple


# This method checks that the solution is a valid solution. It is that the selected list of items does not weight more than the knapsack capacity
def check_solution(capacity, items, taken):
    weight = 0
    value = 0
    for item in items:
        if taken[item.index] == 1:
            weight += item.weight
            value += item.value
    if weight > capacity:
        print(
            "Incorrect solution, the knapsack capacity is exceeded: Capacity = %f, Weight = %f"
            % (capacity, weight)
        )
        return 0
    return value


# El código a continuación debe ser modificado para implementar una solución basada en [**programación dinámica**](https://es.wikipedia.org/wiki/Programaci%C3%B3n_din%C3%A1mica) que utilice en la medida de lo posible funciones lambda
def solve_with_dp_tabulation(items, capacity):
    """Write here your implementation of dynamic programming with tabulation"""
    value = 0
    weight = 0
    taken = [0] * len(items)
    # write here your implementation of dynamic programming
    # prepare the solution in the specified output format
    output_data = str(value) + " " + str(0) + "\n"
    output_data += " ".join(map(str, taken))
    return output_data, check_solution(capacity, items, taken)


# Optativamente, puede implementar programación dinámica con memoization. Recuerde modificar las condiciones de llamada a estas funciones en solve_it
def solve_with_dp_memoization(items, capacity):
    """Write here your implementation of dynamic programming with memoization. This part is optional but will improve your scoring"""
    value = 0
    weight = 0
    taken = [0] * len(items)
    # write here your implementation of dynamic programming
    # prepare the solution in the specified output format
    output_data = str(value) + " " + str(0) + "\n"
    output_data += " ".join(map(str, taken))
    return output_data, check_solution(capacity, items, taken)


# Aquí debe copiar el código implementado en la P2 para que sea invocado cuando la tabla de la programación dinámica se estime muy grande
def solve_with_greedy(items, capacity):
    """Copy here the implementation of greedy you did in P2"""
    pass


# Aquí debe copiar el código implementado del sort de la P2
def sort(items, cmp):
    """Copy here the implementation of sort you did in P2"""
    pass


# This function takes input data that describes a specific problem of TSP and solve it
def solve_it(input_data):
    # parse the input
    lines = input_data.split("\n")
    firstLine = lines[0].split()
    item_count = int(firstLine[0])
    capacity = int(firstLine[1])
    items = []
    for i in range(1, item_count + 1):
        line = lines[i]
        parts = line.split()
        items.append(Item(i - 1, int(parts[0]), int(parts[1])))
    # Modify this code to adapt it to your solution. Currently
    # tabulation is unconditionally invoked, and therefore it
    # will fail with cases requiring a large table.
    # In order to avoid that problem, add here code which helps
    # deciding what approach must be taken (for example, depending
    # on the number of elements of the table), and adjust the
    # conditions of the following if-statement to choose what
    # function must be dynamically invoked: tabulation,
    # memoization or greedy.
    if True:
        return solve_with_dp_tabulation(items, capacity)
    # elif True:
    #    return solve_with_dp_memoization(items, capacity)
    else:
        return solve_with_greedy(items, capacity)


# For each input file, solve_it is called and the result serialized in the ouputs for kaggle and moodle
str_output_kaggle = [["Filename", "Max_value"]]
str_output_moodle = [["Filename", "Max_value", "Solution"]]
for dirname, _, filenames in os.walk("/kaggle/input"):
    for filename in filenames:
        full_name = dirname + "/" + filename
        with open(full_name, "r") as input_data_file:
            input_data = input_data_file.read()
            output, value = solve_it(input_data)
            str_output_kaggle.append([filename, str(value)])
            str_output_moodle.append([filename, str(value), output.split("\n")[1]])
from IPython.display import FileLink


def submission_generation(filename, str_output):
    os.chdir(r"/kaggle/working")
    with open(filename, "w", newline="") as file:
        writer = csv.writer(file)
        for item in str_output:
            writer.writerow(item)
    return FileLink(filename)


submission_generation("NAME_P4_kaggle.csv", str_output_kaggle)
# The file generated by this method must be uploaded in the task of the "campus virtual". The file to upload in the "campus virtual" must be the one related to one submitted to Kaggle. That is, both submitted files must be generated in the same run
submission_generation("NAME_P4_moodle.csv", str_output_moodle)
