plusieurs contraintes de sac à dos

Question

J'ai une question de programmation dynamique que j'ai passé des heures à rechercher en vain.

La première partie est facile: vous avez un sac à dos d'articles, et vous devez maximiser la valeur de ces articles, tout en les gardant en dessous d'un certain poids.

La deuxième partie de la question est la même, sauf qu'il y a maintenant une limite d'article. Ainsi, par exemple:

Quelle est la valeur maximale des articles que vous pourriez mettre dans le sac de sorte que la valeur soit maximisée avec le poids et la limite d'article?

Je ne sais pas comment implémenter la deuxième partie de cette question, je cherche un algorithme général.

Answer 1

Dans la programmation dynamique solution sans limite d'article, vous avez une matrice 2D où l'axe Y est l'indice d'article et l'axe X est le poids. Ensuite, pour chaque paire de poids que vous choisissez maximum entre

valeur
• de poids, y compris l'article si l'article poids < = limite poids
valeur
• de poids hors article

est ici par exemple de la solution standard Python:

def knapsack(n, weight, values, weights): 
    dp = [[0] * (weight + 1) for _ in range(n + 1)] 

    for y in range(1, n + 1): 
     for x in range(weight + 1): 
      if weights[y - 1] <= x: 
       dp[y][x] = max(dp[y - 1][x], 
           dp[y - 1][x - weights[y - 1]] + values[y - 1]) 
      else: 
       dp[y][x] = dp[y - 1][x] 

    return dp[-1][-1] 

maintenant, lorsque vous ajoutez la limite de l'article, vous devez choisir la valeur maximale de chaque élément, la valeur, le nombre d'articles utilisés voyage laisser de

• valeur de poids et n éléments dont l'article si l'article poids < = limite de poids
valeur
• de poids et de n éléments excluant l'élément

Afin de représenter le nombre d'articles que vous pouvez juste ajouter la troisième dimension à la matrice utilisée précédemment qui représente le nombre d'éléments utilisés:

def knapsack2(n, weight, count, values, weights): 
    dp = [[[0] * (weight + 1) for _ in range(n + 1)] for _ in range(count + 1)] 
    for z in range(1, count + 1): 
     for y in range(1, n + 1): 
      for x in range(weight + 1): 
       if weights[y - 1] <= x: 
        dp[z][y][x] = max(dp[z][y - 1][x], 
             dp[z - 1][y - 1][x - weights[y - 1]] + values[y - 1]) 
       else: 
        dp[z][y][x] = dp[z][y - 1][x] 

    return dp[-1][-1][-1] 

démonstration simple:

w = 5 
k = 2 
values = [1, 2, 3, 2, 2] 
weights = [4, 5, 1, 1, 1] 
n = len(values) 

no_limit_fmt = 'Max value for weight limit {}, no item limit: {}' 
limit_fmt = 'Max value for weight limit {}, item limit {}: {}' 

print(no_limit_fmt.format(w, knapsack(n, w, values, weights))) 
print(limit_fmt.format(w, k, knapsack2(n, w, k, values, weights))) 

Sortie:

Max value for weight limit 5, no item limit: 7 
Max value for weight limit 5, item limit 2: 5 

Notez que vous pouvez optimiser un peu l'exemple en ce qui concerne la consommation de mémoire depuis lors de l'ajout élément ZTH à la solution que vous avez seulement besoin de connaître la solution pour z - 1 articles. En outre, vous pouvez vérifier s'il est possible d'ajuster z éléments sous la limite de poids pour commencer et si non, réduire la limite de l'article en conséquence.