Mochila ilimitada (se permite la repetición de artículos) – Part 1

Dado un peso de mochila W y un conjunto de n artículos con cierto valor val i y peso wt i , necesitamos calcular la cantidad máxima que podría formar exactamente esta cantidad. Esto es diferente del clásico problema de la mochila , aquí podemos usar un número ilimitado de instancias de un elemento.
Ejemplos: 

Input : W = 100
       val[]  = {1, 30}
       wt[] = {1, 50}
Output : 100
There are many ways to fill knapsack.
1) 2 instances of 50 unit weight item.
2) 100 instances of 1 unit weight item.
3) 1 instance of 50 unit weight item and 50
   instances of 1 unit weight items.
We get maximum value with option 2.

Input : W = 8
       val[] = {10, 40, 50, 70}
       wt[]  = {1, 3, 4, 5}       
Output : 110 
We get maximum value with one unit of
weight 5 and one unit of weight 3.

Enfoque recursivo: 

Una solución simple es considerar todos los subconjuntos de artículos y calcular el peso total y el valor de todos los subconjuntos. Considere los únicos subconjuntos cuyo peso total es menor que W. De todos esos subconjuntos, elija el subconjunto de valor máximo.
Subestructura óptima: para considerar todos los subconjuntos de elementos, puede haber dos casos para cada elemento.

Caso 1: El artículo está incluido en el subconjunto óptimo.
Caso 2: El artículo no está incluido en el conjunto óptimo.
Por lo tanto, el valor máximo que se puede obtener de ‘n’ elementos es el máximo de los siguientes dos valores.

Valor máximo obtenido por n-1 ítems y peso W (excluyendo el n-ésimo ítem).
Valor del n-ésimo artículo más el valor máximo obtenido por n (debido a la oferta infinita) artículos y W menos el peso del n-ésimo artículo (incluido el n-ésimo artículo).
Si el peso del elemento ‘n-ésimo’ es mayor que ‘W’, entonces el elemento n-ésimo no se puede incluir y el Caso 1 es la única posibilidad.

A continuación se muestra la implementación del enfoque anterior: 

Python3

# Python3 program to find maximum
# achievable value with a knapsack
# of weight W and multiple instances allowed.
 
# Returns the maximum value
# with knapsack of W capacity
# A Naive recursive implementation of unbounded Knapsack problem
def unboundedKnapsack(W, index, val, wt):
 
    #Base case of recursion when only one element is there.
    if index==0 :return (W//wt[0])*val[0]
    #If the element with referred by index is doesn't occur even once in the required solution
    notTake=0+unboundedKnapsack(W,index-1,val,wt)
    #If the element is occur atleast once in the required solution
    take=-100000
    if wt[index]<=W:
        take=val[index]+unboundedKnapsack(W-wt[index],index,val,wt)
    return max(take,notTake)   
 
 
# Driver program
W = 100
val = [10, 30, 20]
wt = [5, 10, 15]
n = len(val)
 
print(unboundedKnapsack(W, n-1, val, wt))

C++

/* A Naive recursive implementation of
unbounded Knapsack problem */
#include <bits/stdc++.h>
using namespace std;
 
// Returns the maximum value that
// can be put in a knapsack of capacity W
int unboundedKnapsack(int W, int wt[], int val[], int idx)
{
 
    // Base Case
    // if we are at idx 0.
    if (idx == 0) {
        return (W / wt[0]) * val[0];
    }
    // There are two cases either take element or not take.
    // If not take then
    int notTake
        = 0 + unboundedKnapsack(W, wt, val, idx - 1);
    // if take then weight = W-wt[idx] and index will remain
    // same.
    int take = INT_MIN;
    if (wt[idx] <= W) {
        take = val[idx]
            + unboundedKnapsack(W - wt[idx], wt, val,
                                idx);
    }
    return max(take, notTake);
}
 
// Driver code
int main()
{
    int W = 100;
    int val[] = { 10, 30, 20 };
    int wt[] = { 5, 10, 15 };
    int n = sizeof(val) / sizeof(val[0]);
 
    cout << unboundedKnapsack(W, wt, val, n - 1);
    return 0;
}
// This code is contributed by Sanskar.

Java

class Knapsack {
 
    // A utility function that returns
    // maximum of two integers
    static int max(int a, int b) { return (a > b) ? a : b; }
 
    // Returns the maximum value that
    // can be put in a knapsack of
    // capacity W
    static int unboundedKnapsack(int W, int wt[], int val[],
                                int idx)
    {
        // Base Case
        // if we are at idx 0.
        if (idx == 0) {
            return (W / wt[0]) * val[0];
        }
        // There are two cases either take element or not
        // take. If not take then
        int notTake
            = 0 + unboundedKnapsack(W, wt, val, idx - 1);
        // if take then weight = W-wt[idx] and index will
        // remain same.
        int take = Integer.MIN_VALUE;
        if (wt[idx] <= W) {
            take = val[idx]
                + unboundedKnapsack(W - wt[idx], wt, val,
                                    idx);
        }
        return max(take, notTake);
    }
 
    // Driver code
    public static void main(String args[])
    {
        int W = 100;
        int val[] = { 10, 30, 20 };
        int wt[] = { 5, 10, 15 };
        int n = val.length;
        System.out.println(
            unboundedKnapsack(W, wt, val, n - 1));
    }
}
// This code is contributed by Sanskar.
Producción

300

Memoización:  Al igual que otros problemas típicos de Programación Dinámica (DP), el recálculo de los mismos subproblemas se puede evitar construyendo una array temporal K[][] de forma ascendente. A continuación se muestra la implementación basada en la programación dinámica.

C++

/* A Naive recursive implementation of
 unbounded Knapsack problem */
#include <bits/stdc++.h>
using namespace std;
 
// Returns the maximum value that
// can be put in a knapsack of capacity W
int unboundedKnapsack(int W, int wt[], int val[], int idx,
                      vector<vector<int> >& dp)
{
 
    // Base Case
    // if we are at idx 0.
    if (idx == 0) {
        return (W / wt[0]) * val[0];
    }
    // If the value is already calculated then we will
    // previous calculated value
    if (dp[idx][W] != -1)
        return dp[idx][W];
    // There are two cases either take element or not take.
    // If not take then
 
    int notTake
        = 0 + unboundedKnapsack(W, wt, val, idx - 1, dp);
    // if take then weight = W-wt[idx] and index will remain
    // same.
    int take = INT_MIN;
    if (wt[idx] <= W) {
        take = val[idx]
               + unboundedKnapsack(W - wt[idx], wt, val,
                                   idx, dp);
    }
    return dp[idx][W] = max(take, notTake);
}
 
// Driver code
int main()
{
    int W = 100;
    int val[] = { 10, 30, 20 };
    int wt[] = { 5, 10, 15 };
    int n = sizeof(val) / sizeof(val[0]);
    vector<vector<int> > dp(n, vector<int>(W + 1, -1));
    cout << unboundedKnapsack(W, wt, val, n - 1, dp);
    return 0;
}
// This code is contributed by Sanskar.

Java

import java.util.Arrays;
class Knapsack {
 
    // A utility function that returns
    // maximum of two integers
    static int max(int a, int b) { return (a > b) ? a : b; }
 
    // Returns the maximum value that
    // can be put in a knapsack of
    // capacity W
    static int unboundedKnapsack(int W, int wt[], int val[],
                                 int idx, int dp[][])
    {
        // Base Case
        // if we are at idx 0.
        if (idx == 0) {
            return (W / wt[0]) * val[0];
        }
 
        // If the value is already calculated then we will
        // previous calculated value
        if (dp[idx][W] != -1)
            return dp[idx][W];
        // There are two cases either take element or not
        // take. If not take then
        int notTake
            = 0
              + unboundedKnapsack(W, wt, val, idx - 1, dp);
        // if take then weight = W-wt[idx] and index will
        // remain same.
        int take = Integer.MIN_VALUE;
        if (wt[idx] <= W) {
            take = val[idx]
                   + unboundedKnapsack(W - wt[idx], wt, val,
                                       idx, dp);
        }
        return dp[idx][W] = max(take, notTake);
    }
 
    // Driver code
    public static void main(String args[])
    {
        int W = 100;
        int val[] = { 10, 30, 20 };
        int wt[] = { 5, 10, 15 };
        int n = val.length;
        int[][] dp = new int[n][W + 1];
        for (int row[] : dp)
            Arrays.fill(row, -1);
        System.out.println(
            unboundedKnapsack(W, wt, val, n - 1, dp));
    }
}
// This code is contributed by Sanskar.
Producción

300

Complejidad de tiempo: O(N*W)

Complejidad espacial: O(N*W) + O(N)’

Programación Dinámica: Es un problema de mochila ilimitado ya que podemos usar 1 o más instancias de cualquier recurso. Se puede usar una array 1D simple, digamos dp [W + 1], de modo que dp [i] almacene el valor máximo que se puede lograr usando todos los artículos y la capacidad i de la mochila. Tenga en cuenta que aquí usamos una array 1D, que es diferente de la mochila clásica donde usamos una array 2D. Aquí el número de artículos nunca cambia. Siempre tenemos todos los artículos disponibles.
Podemos calcular recursivamente dp[] usando la siguiente fórmula

dp[i] = 0
dp[i] = max(dp[i], dp[i-wt[j]] + val[j] 
                   where j varies from 0 
                   to n-1 such that:
                   wt[j] <= i

result = d[W]

A continuación se muestra la implementación de la idea anterior. 

C++

// C++ program to find maximum achievable value
// with a knapsack of weight W and multiple
// instances allowed.
#include<bits/stdc++.h>
using namespace std;
 
// Returns the maximum value with knapsack of
// W capacity
int unboundedKnapsack(int W, int n,
                       int val[], int wt[])
{
    // dp[i] is going to store maximum value
    // with knapsack capacity i.
    int dp[W+1];
    memset(dp, 0, sizeof dp);
 
    // Fill dp[] using above recursive formula
    for (int i=0; i<=W; i++)
      for (int j=0; j<n; j++)
         if (wt[j] <= i)
            dp[i] = max(dp[i], dp[i-wt[j]] + val[j]);
 
    return dp[W];
}
 
// Driver program
int main()
{
    int W = 100;
    int val[] = {10, 30, 20};
    int wt[] = {5, 10, 15};
    int n = sizeof(val)/sizeof(val[0]);
 
    cout << unboundedKnapsack(W, n, val, wt);
 
    return 0;
}

Java

// Java program to find maximum achievable
// value with a knapsack of weight W and
// multiple instances allowed.
public class UboundedKnapsack
{
     
    private static int max(int i, int j)
    {
            return (i > j) ? i : j;
    }
     
    // Returns the maximum value with knapsack
    // of W capacity
    private static int unboundedKnapsack(int W, int n,
                                int[] val, int[] wt)
    {
         
        // dp[i] is going to store maximum value
        // with knapsack capacity i.
        int dp[] = new int[W + 1];
         
        // Fill dp[] using above recursive formula
        for(int i = 0; i <= W; i++){
            for(int j = 0; j < n; j++){
                if(wt[j] <= i){
                    dp[i] = max(dp[i], dp[i - wt[j]] +
                                val[j]);
                }
            }
        }
        return dp[W];
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int W = 100;
        int val[] = {10, 30, 20};
        int wt[] = {5, 10, 15};
        int n = val.length;
        System.out.println(unboundedKnapsack(W, n, val, wt));
    }
}
// This code is contributed by Aditya Kumar

Python3

# Python3 program to find maximum
# achievable value with a knapsack
# of weight W and multiple instances allowed.
 
# Returns the maximum value
# with knapsack of W capacity
def unboundedKnapsack(W, n, val, wt):
 
    # dp[i] is going to store maximum
    # value with knapsack capacity i.
    dp = [0 for i in range(W + 1)]
 
    ans = 0
 
    # Fill dp[] using above recursive formula
    for i in range(W + 1):
        for j in range(n):
            if (wt[j] <= i):
                dp[i] = max(dp[i], dp[i - wt[j]] + val[j])
 
    return dp[W]
 
# Driver program
W = 100
val = [10, 30, 20]
wt = [5, 10, 15]
n = len(val)
 
print(unboundedKnapsack(W, n, val, wt))
 
# This code is contributed by Anant Agarwal.

C#

// C# program to find maximum achievable
// value with a knapsack of weight W and
// multiple instances allowed.
using System;
 
class UboundedKnapsack {
     
    private static int max(int i, int j)
    {
            return (i > j) ? i : j;
    }
     
    // Returns the maximum value
    // with knapsack of W capacity
    private static int unboundedKnapsack(int W, int n,
                                  int []val, int []wt)
    {
         
        // dp[i] is going to store maximum value
        // with knapsack capacity i.
        int []dp = new int[W + 1];
         
        // Fill dp[] using above recursive formula
        for(int i = 0; i <= W; i++){
            for(int j = 0; j < n; j++){
                if(wt[j] <= i){
                    dp[i] = Math.Max(dp[i], dp[i -
                                        wt[j]] + val[j]);
                }
            }
        }
        return dp[W];
    }
 
    // Driver program
    public static void Main()
    {
        int W = 100;
        int []val = {10, 30, 20};
        int []wt = {5, 10, 15};
        int n = val.Length;
        Console.WriteLine(unboundedKnapsack(W, n, val, wt));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find maximum
// achievable value with a
// knapsack of weight W and
// multiple instances allowed.
 
// Returns the maximum value
// with knapsack of W capacity
function unboundedKnapsack($W, $n,
                           $val, $wt)
{
    // dp[i] is going to store
    // maximum value with
    // knapsack capacity i.
    for($i = 0; $i <= $W; $i++)
        $dp[$i] = 0;
 
    $ans = 0;
     
    // Fill dp[] using above
    // recursive formula
    for ($i = 0; $i <= $W; $i++)
    for ($j = 0; $j < $n; $j++)
        if ($wt[$j] <= $i)
            $dp[$i] = max($dp[$i],
                          $dp[$i - $wt[$j]] +
                                   $val[$j]);
 
    return $dp[$W];
}
 
// Driver Code
$W = 100;
$val = array(10, 30, 20);
$wt = array(5, 10, 15);
$n = count($val); //sizeof($val)/sizeof($val[0]);
 
echo unboundedKnapsack($W, $n,
                       $val, $wt);
 
// This code is contributed
// by shiv_bhakt
?>

Javascript

<script>
    // Javascript program to find maximum achievable
    // value with a knapsack of weight W and
    // multiple instances allowed.
     
    function max(i, j)
    {
            return (i > j) ? i : j;
    }
      
    // Returns the maximum value
    // with knapsack of W capacity
    function unboundedKnapsack(W, n, val, wt)
    {
          
        // dp[i] is going to store maximum value
        // with knapsack capacity i.
        let dp = new Array(W + 1);
        dp.fill(0);
          
        // Fill dp[] using above recursive formula
        for(let i = 0; i <= W; i++){
            for(let j = 0; j < n; j++){
                if(wt[j] <= i){
                    dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
                }
            }
        }
        return dp[W];
    }
     
    let W = 100;
    let val = [10, 30, 20];
    let wt = [5, 10, 15];
    let n = val.length;
    document.write(unboundedKnapsack(W, n, val, wt));
     
</script>
Producción

300

Complejidad de tiempo: O(W*N) donde W es el peso total (capacidad) y N es el número total de artículos.
Espacio Auxiliar: O(W) donde W es el peso total.

Este artículo está compilado usando aportes de Shubham Gupta , Shubham Joshi y Ashish kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *