0-1 Problema de mochila | DP-10 – Part 2

Dados los pesos y valores de n artículos, coloque estos artículos en una mochila de capacidad W para obtener el valor total máximo en la mochila. En otras palabras, dadas dos arrays de enteros val[0..n-1] y wt[0..n-1] que representan valores y pesos asociados con n elementos respectivamente. También dado un número entero W que representa la capacidad de la mochila, averigüe el subconjunto de valor máximo de val[] tal que la suma de los pesos de este subconjunto sea menor o igual a W. No puede romper un artículo, elegir el artículo completo o no no elegirlo (propiedad 0-1).

knapsack-problem

C++

/* A Naive recursive implementation of
 0-1 Knapsack problem */
#include <bits/stdc++.h>
using namespace std;
 
// A utility function that returns
// maximum of two integers
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
int knapSack(int W, int wt[], int val[], int n)
{
 
    // Base Case
    if (n == 0 || W == 0)
        return 0;
 
    // If weight of the nth item is more
    // than Knapsack capacity W, then
    // this item cannot be included
    // in the optimal solution
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);
 
    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else
        return max(
            val[n - 1]
                + knapSack(W - wt[n - 1],
                           wt, val, n - 1),
            knapSack(W, wt, val, n - 1));
}
 
// Driver code
int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    cout << knapSack(W, wt, val, n);
    return 0;
}
 
// This code is contributed by rathbhupendra

C

/* A Naive recursive implementation
of 0-1 Knapsack problem */
#include <stdio.h>
 
// A utility function that returns
// maximum of two integers
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
int knapSack(int W, int wt[], int val[], int n)
{
    // Base Case
    if (n == 0 || W == 0)
        return 0;
 
    // If weight of the nth item is more than
    // Knapsack capacity W, then this item cannot
    // be included in the optimal solution
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);
 
    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else
        return max(
            val[n - 1]
                + knapSack(W - wt[n - 1],
                           wt, val, n - 1),
            knapSack(W, wt, val, n - 1));
}
 
// Driver program to test above function
int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}

Java

/* A Naive recursive implementation
of 0-1 Knapsack problem */
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 knapSack(int W, int wt[], int val[], int n)
    {
        // Base Case
        if (n == 0 || W == 0)
            return 0;
 
        // If weight of the nth item is
        // more than Knapsack capacity W,
        // then this item cannot be included
        // in the optimal solution
        if (wt[n - 1] > W)
            return knapSack(W, wt, val, n - 1);
 
        // Return the maximum of two cases:
        // (1) nth item included
        // (2) not included
        else
            return max(val[n - 1]
                       + knapSack(W - wt[n - 1], wt,
                                  val, n - 1),
                       knapSack(W, wt, val, n - 1));
    }
 
    // Driver code
    public static void main(String args[])
    {
        int val[] = new int[] { 60, 100, 120 };
        int wt[] = new int[] { 10, 20, 30 };
        int W = 50;
        int n = val.length;
        System.out.println(knapSack(W, wt, val, n));
    }
}
/*This code is contributed by Rajat Mishra */

Python

# A naive recursive implementation
# of 0-1 Knapsack Problem
 
# Returns the maximum value that
# can be put in a knapsack of
# capacity W
 
 
def knapSack(W, wt, val, n):
 
    # Base Case
    if n == 0 or W == 0:
        return 0
 
    # If weight of the nth item is
    # more than Knapsack of capacity W,
    # then this item cannot be included
    # in the optimal solution
    if (wt[n-1] > W):
        return knapSack(W, wt, val, n-1)
 
    # return the maximum of two cases:
    # (1) nth item included
    # (2) not included
    else:
        return max(
            val[n-1] + knapSack(
                W-wt[n-1], wt, val, n-1),
            knapSack(W, wt, val, n-1))
 
# end of function knapSack
 
 
#Driver Code
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print knapSack(W, wt, val, n)
 
# This code is contributed by Nikhil Kumar Singh

C#

/* A Naive recursive implementation of
0-1 Knapsack problem */
using System;
 
class GFG {
 
    // 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 knapSack(int W, int[] wt,
                        int[] val, int n)
    {
 
        // Base Case
        if (n == 0 || W == 0)
            return 0;
 
        // If weight of the nth item is
        // more than Knapsack capacity W,
        // then this item cannot be
        // included in the optimal solution
        if (wt[n - 1] > W)
            return knapSack(W, wt,
                            val, n - 1);
 
        // Return the maximum of two cases:
        // (1) nth item included
        // (2) not included
        else
            return max(val[n - 1]
                       + knapSack(W - wt[n - 1], wt,
                                  val, n - 1),
                       knapSack(W, wt, val, n - 1));
    }
 
    // Driver code
    public static void Main()
    {
        int[] val = new int[] { 60, 100, 120 };
        int[] wt = new int[] { 10, 20, 30 };
        int W = 50;
        int n = val.Length;
 
        Console.WriteLine(knapSack(W, wt, val, n));
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// A Naive recursive implementation
// of 0-1 Knapsack problem
 
// Returns the maximum value that
// can be put in a knapsack of
// capacity W
function knapSack($W, $wt, $val, $n)
{
    // Base Case
    if ($n == 0 || $W == 0)
        return 0;
     
    // If weight of the nth item is
    // more than Knapsack capacity
    // W, then this item cannot be
    // included in the optimal solution
    if ($wt[$n - 1] > $W)
        return knapSack($W, $wt, $val, $n - 1);
     
    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else
        return max($val[$n - 1] +
               knapSack($W - $wt[$n - 1],
               $wt, $val, $n - 1),
               knapSack($W, $wt, $val, $n-1));
}
 
    // Driver Code
    $val = array(60, 100, 120);
    $wt = array(10, 20, 30);
    $W = 50;
    $n = count($val);
    echo knapSack($W, $wt, $val, $n);
 
// This code is contributed by Sam007
?>

Javascript

<script>
 
    /* A Naive recursive implementation of
    0-1 Knapsack problem */
     
    // A utility function that returns
    // maximum of two integers
    function max(a, b)
    {
         return (a > b) ? a : b;
    }
  
    // Returns the maximum value that can
    // be put in a knapsack of capacity W
    function knapSack(W, wt, val, n)
    {
  
        // Base Case
        if (n == 0 || W == 0)
            return 0;
  
        // If weight of the nth item is
        // more than Knapsack capacity W,
        // then this item cannot be
        // included in the optimal solution
        if (wt[n - 1] > W)
            return knapSack(W, wt, val, n - 1);
  
        // Return the maximum of two cases:
        // (1) nth item included
        // (2) not included
        else
            return max(val[n - 1] +
            knapSack(W - wt[n - 1], wt, val, n - 1),
            knapSack(W, wt, val, n - 1));
    }
       
    let val = [ 60, 100, 120 ];
    let wt = [ 10, 20, 30 ];
       let W = 50;
    let n = val.length;
 
    document.write(knapSack(W, wt, val, n));
     
</script>

C++

// A dynamic programming based
// solution for 0-1 Knapsack problem
#include <bits/stdc++.h>
using namespace std;
 
// A utility function that returns
// maximum of two integers
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
int knapSack(int W, int wt[], int val[], int n)
{
    int i, w;
      vector<vector<int>> K(n + 1, vector<int>(W + 1));
 
    // Build table K[][] in bottom up manner
    for(i = 0; i <= n; i++)
    {
        for(w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] +
                                K[i - 1][w - wt[i - 1]],
                                K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
    return K[n][W];
}
 
// Driver Code
int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
     
    cout << knapSack(W, wt, val, n);
     
    return 0;
}
 
// This code is contributed by Debojyoti Mandal

C

// A Dynamic Programming based
// solution for 0-1 Knapsack problem
#include <stdio.h>
 
// A utility function that returns
// maximum of two integers
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
int knapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    int K[n + 1][W + 1];
 
    // Build table K[][] in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1]
                          + K[i - 1][w - wt[i - 1]],
                          K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
 
    return K[n][W];
}
 
// Driver Code
int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}

Java

// A Dynamic Programming based solution
// for 0-1 Knapsack problem
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 knapSack(int W, int wt[],
                        int val[], int n)
    {
        int i, w;
        int K[][] = new int[n + 1][W + 1];
 
        // Build table K[][] in bottom up manner
        for (i = 0; i <= n; i++)
        {
            for (w = 0; w <= W; w++)
            {
                if (i == 0 || w == 0)
                    K[i][w] = 0;
                else if (wt[i - 1] <= w)
                    K[i][w]
                        = max(val[i - 1]
                         + K[i - 1][w - wt[i - 1]],
                         K[i - 1][w]);
                else
                    K[i][w] = K[i - 1][w];
            }
        }
 
        return K[n][W];
    }
 
    // Driver code
    public static void main(String args[])
    {
        int val[] = new int[] { 60, 100, 120 };
        int wt[] = new int[] { 10, 20, 30 };
        int W = 50;
        int n = val.length;
        System.out.println(knapSack(W, wt, val, n));
    }
}
/*This code is contributed by Rajat Mishra */

Python

# A Dynamic Programming based Python
# Program for 0-1 Knapsack problem
# Returns the maximum value that can
# be put in a knapsack of capacity W
 
 
def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
 
    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1]
                          + K[i-1][w-wt[i-1]], 
                              K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
 
    return K[n][W]
 
 
# Driver code
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))
 
# This code is contributed by Bhavya Jain

C#

// A Dynamic Programming based solution for
// 0-1 Knapsack problem
using System;
 
class GFG {
 
    // 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 knapSack(int W, int[] wt,
                        int[] val, int n)
    {
        int i, w;
        int[, ] K = new int[n + 1, W + 1];
 
        // Build table K[][] in bottom
        // up manner
        for (i = 0; i <= n; i++)
        {
            for (w = 0; w <= W; w++)
            {
                if (i == 0 || w == 0)
                    K[i, w] = 0;
                 
                else if (wt[i - 1] <= w)
                    K[i, w] = Math.Max(
                        val[i - 1]
                        + K[i - 1, w - wt[i - 1]],
                        K[i - 1, w]);
                else
                    K[i, w] = K[i - 1, w];
            }
        }
 
        return K[n, W];
    }
 
    // Driver code
    static void Main()
    {
        int[] val = new int[] { 60, 100, 120 };
        int[] wt = new int[] { 10, 20, 30 };
        int W = 50;
        int n = val.Length;
 
        Console.WriteLine(knapSack(W, wt, val, n));
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// A Dynamic Programming based solution
// for 0-1 Knapsack problem
 
// Returns the maximum value that
// can be put in a knapsack of
// capacity W
function knapSack($W, $wt, $val, $n)
{
     
    $K = array(array());
     
    // Build table K[][] in
    // bottom up manner
    for ($i = 0; $i <= $n; $i++)
    {
        for ($w = 0; $w <= $W; $w++)
        {
            if ($i == 0 || $w == 0)
                $K[$i][$w] = 0;
            else if ($wt[$i - 1] <= $w)
                    $K[$i][$w] = max($val[$i - 1] +
                                     $K[$i - 1][$w -
                                     $wt[$i - 1]],
                                     $K[$i - 1][$w]);
            else
                    $K[$i][$w] = $K[$i - 1][$w];
        }
    }
     
    return $K[$n][$W];
}
 
    // Driver Code
    $val = array(60, 100, 120);
    $wt = array(10, 20, 30);
    $W = 50;
    $n = count($val);
    echo knapSack($W, $wt, $val, $n);
     
// This code is contributed by Sam007.
?>

Javascript

<script>
    // A Dynamic Programming based solution
    // for 0-1 Knapsack problem
     
    // A utility function that returns
    // maximum of two integers
    function max(a, b)
    {
          return (a > b) ? a : b;
    }
  
    // Returns the maximum value that can
    // be put in a knapsack of capacity W
    function knapSack(W, wt, val, n)
    {
        let i, w;
        let K = new Array(n + 1);
  
        // Build table K[][] in bottom up manner
        for (i = 0; i <= n; i++)
        {
            K[i] = new Array(W + 1);
            for (w = 0; w <= W; w++)
            {
                if (i == 0 || w == 0)
                    K[i][w] = 0;
                else if (wt[i - 1] <= w)
                    K[i][w]
                        = max(val[i - 1]
                         + K[i - 1][w - wt[i - 1]],
                         K[i - 1][w]);
                else
                    K[i][w] = K[i - 1][w];
            }
        }
  
        return K[n][W];
    }
     
    let val = [ 60, 100, 120 ];
    let wt = [ 10, 20, 30 ];
    let W = 50;
    let n = val.length;
    document.write(knapSack(W, wt, val, n));
</script>

C++

#include <bits/stdc++.h>
using namespace std;
 
// we can further improve the above Knapsack function's space
// complexity
int knapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    int K[2][W + 1];
    // We know we are always using the current row or
    // the previous row of the array/vector . Thereby we can
    // improve it further by using a 2D array but with only
    // 2 rows i%2 will be giving the index inside the bounds
    // of 2d array K
 
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                K[i % 2][w] = 0;
            else if (wt[i - 1] <= w)
                K[i % 2][w] = max(
                    val[i - 1]
                        + K[(i - 1) % 2][w - wt[i - 1]],
                    K[(i - 1) % 2][w]);
            else
                K[i % 2][w] = K[(i - 1) % 2][w];
        }
    }
    return K[n % 2][W];
}
 
// Driver Code
int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
 
    cout << knapSack(W, wt, val, n);
 
    return 0;
}
 
// This code was improved by Udit Singla

Java

import java.util.*;
class GFG {
 
  // we can further improve the above Knapsack function's space
  // complexity
  static int knapSack(int W, int wt[], int val[], int n)
  {
    int i, w;
    int [][]K = new int[2][W + 1];
     
    // We know we are always using the current row or
    // the previous row of the array/vector . Thereby we can
    // improve it further by using a 2D array but with only
    // 2 rows i%2 will be giving the index inside the bounds
    // of 2d array K
    for (i = 0; i <= n; i++) {
      for (w = 0; w <= W; w++) {
        if (i == 0 || w == 0)
          K[i % 2][w] = 0;
        else if (wt[i - 1] <= w)
          K[i % 2][w] = Math.max(
          val[i - 1]
          + K[(i - 1) % 2][w - wt[i - 1]],
          K[(i - 1) % 2][w]);
        else
          K[i % 2][w] = K[(i - 1) % 2][w];
      }
    }
    return K[n % 2][W];
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = val.length;
 
    System.out.print(knapSack(W, wt, val, n));
 
  }
}
 
// This code is contributed by gauravrajput1

Python3

# we can further improve the above Knapsack function's space
# complexity
def knapSack(W, wt, val, n):
 
    K = [[0 for x in range(W+1)] for y in range(2)]
     
    # We know we are always using the  current row or
    # the previous row of the array/vector . Thereby we can
    # improve it further by using a 2D array but with only
    # 2 rows i%2 will be giving the index inside the bounds
    # of 2d array K
    for i in range(n + 1):
        for w in range(W + 1):
            if (i == 0 or w == 0):
                K[i % 2][w] = 0
            elif (wt[i - 1] <= w):
                K[i % 2][w] = max(
                    val[i - 1]
                    + K[(i - 1) % 2][w - wt[i - 1]],
                    K[(i - 1) % 2][w])
 
            else:
                K[i % 2][w] = K[(i - 1) % 2][w]
 
    return K[n % 2][W]
 
# Driver Code
if __name__ == "__main__":
 
    val = [60, 100, 120]
    wt = [10, 20, 30]
    W = 50
    n = len(val)
 
    print(knapSack(W, wt, val, n))
 
    # This code is contributed by ukasp.

C#

using System;
 
public class GFG {
 
    // we can further improve the above Knapsack function's space
    // complexity
    static int knapSack(int W, int []wt, int []val, int n) {
        int i, w;
        int[,] K = new int[2,W + 1];
 
        // We know we are always using the  current row or
        // the previous row of the array/vector . Thereby we can
        // improve it further by using a 2D array but with only
        // 2 rows i%2 will be giving the index inside the bounds
        // of 2d array K
        for (i = 0; i <= n; i++) {
            for (w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    K[i % 2, w] = 0;
                else if (wt[i - 1] <= w)
                    K[i % 2,w] = Math.Max(val[i - 1] + K[(i - 1) % 2,w - wt[i - 1]], K[(i - 1) % 2,w]);
                else
                    K[i % 2,w] = K[(i - 1) % 2,w];
            }
        }
        return K[n % 2,W];
    }
 
    // Driver Code
    public static void Main(String[] args) {
        int []val = { 60, 100, 120 };
        int []wt = { 10, 20, 30 };
        int W = 50;
        int n = val.Length;
 
        Console.Write(knapSack(W, wt, val, n));
 
    }
}
 
// This code is contributed by umadevi9616

Javascript

<script>
    // we can further improve the above Knapsack function's space
    // complexity
    function knapSack(W , wt , val , n) {
        var i, w;
        var K = Array(2).fill().map(()=>Array(W + 1).fill(0));
 
        // We know we are always using the current row or
        // the previous row of the array/vector . Thereby we can
        // improve it further by using a 2D array but with only
        // 2 rows i%2 will be giving the index inside the bounds
        // of 2d array K
        for (i = 0; i <= n; i++) {
            for (w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    K[i % 2][w] = 0;
                else if (wt[i - 1] <= w)
                    K[i % 2][w] = Math.max(val[i - 1] +
                    K[(i - 1) % 2][w - wt[i - 1]],
                    K[(i - 1) % 2][w]);
                else
                    K[i % 2][w] = K[(i - 1) % 2][w];
            }
        }
        return K[n % 2][W];
    }
 
    // Driver Code
        var val = [ 60, 100, 120 ];
        var wt = [ 10, 20, 30 ];
        var W = 50;
        var n = val.length;
 
        document.write(knapSack(W, wt, val, n));
 
// This code is contributed by Rajput-Ji
</script>

C++

// Here is the top-down approach of
// dynamic programming
#include <bits/stdc++.h>
using namespace std;
 
// Returns the value of maximum profit
int knapSackRec(int W, int wt[],
                int val[], int i,
                int** dp)
{
    // base condition
    if (i < 0)
        return 0;
    if (dp[i][W] != -1)
        return dp[i][W];
 
    if (wt[i] > W) {
 
        // Store the value of function call
        // stack in table before return
        dp[i][W] = knapSackRec(W, wt,
                               val, i - 1,
                               dp);
        return dp[i][W];
    }
    else {
        // Store value in a table before return
        dp[i][W] = max(val[i]
                      + knapSackRec(W - wt[i],
                                   wt, val,
                                   i - 1, dp),
                       knapSackRec(W, wt, val,
                                   i - 1, dp));
 
        // Return value of table after storing
        return dp[i][W];
    }
}
 
int knapSack(int W, int wt[], int val[], int n)
{
    // double pointer to declare the
    // table dynamically
    int** dp;
    dp = new int*[n];
 
    // loop to create the table dynamically
    for (int i = 0; i < n; i++)
        dp[i] = new int[W + 1];
 
    // loop to initially filled the
    // table with -1
    for (int i = 0; i < n; i++)
        for (int j = 0; j < W + 1; j++)
            dp[i][j] = -1;
    return knapSackRec(W, wt, val, n - 1, dp);
}
 
// Driver Code
int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    cout << knapSack(W, wt, val, n);
    return 0;
}

Java

// Here is the top-down approach of 
// dynamic programming
class GFG{
     
// A utility function that returns 
// maximum of two integers    
static int max(int a, int b)    
{    
    return (a > b) ? a : b;    
}
 
// Returns the value of maximum profit  
static int knapSackRec(int W, int wt[],
                       int val[], int n,
                       int [][]dp)
{  
     
    // Base condition
    if (n == 0 || W == 0)  
        return 0;
         
    if (dp[n][W] != -1)
        return dp[n][W];  
     
    if (wt[n - 1] > W)  
     
        // Store the value of function call  
        // stack in table before return
        return dp[n][W] = knapSackRec(W, wt, val,
                                      n - 1, dp);
                                       
    else
     
        // Return value of table after storing 
        return dp[n][W] = max((val[n - 1] +
                              knapSackRec(W - wt[n - 1], wt,
                                          val, n - 1, dp)),
                              knapSackRec(W, wt, val,
                                          n - 1, dp));            
}
 
static int knapSack(int W, int wt[], int val[], int N)
{ 
     
    // Declare the table dynamically
    int dp[][] = new int[N + 1][W + 1];
     
    // Loop to initially filled the
    // table with -1
    for(int i = 0; i < N + 1; i++)  
        for(int j = 0; j < W + 1; j++)  
            dp[i][j] = -1;   
     
    return knapSackRec(W, wt, val, N, dp);    
}
 
// Driver Code
public static void main(String [] args)
{      
    int val[] = { 60, 100, 120 };  
    int wt[] = { 10, 20, 30 };  
     
    int W = 50; 
    int N = val.length;        
     
    System.out.println(knapSack(W, wt, val, N));  
}    
}
 
// This Code is contributed By FARAZ AHMAD

Python3

# This is the memoization approach of
# 0 / 1 Knapsack in Python in simple
# we can say recursion + memoization = DP
 
# driver code
val = [60, 100, 120 ]
wt = [10, 20, 30 ]
W = 50
n = len(val)
 
# We initialize the matrix with -1 at first.
t = [[-1 for i in range(W + 1)] for j in range(n + 1)]
 
 
def knapsack(wt, val, W, n):
 
    # base conditions
    if n == 0 or W == 0:
        return 0
    if t[n][W] != -1:
        return t[n][W]
 
    # choice diagram code
    if wt[n-1] <= W:
        t[n][W] = max(
            val[n-1] + knapsack(
                wt, val, W-wt[n-1], n-1),
            knapsack(wt, val, W, n-1))
        return t[n][W]
    elif wt[n-1] > W:
        t[n][W] = knapsack(wt, val, W, n-1)
        return t[n][W]
 
 
print(knapsack(wt, val, W, n))
 
# This code is contributed by Prosun Kumar Sarkar

C#

// Here is the top-down approach of 
// dynamic programming
using System;
public class GFG
{
 
    // A utility function that returns
    // maximum of two integers
    static int max(int a, int b) { return (a > b) ? a : b; }
 
    // Returns the value of maximum profit
    static int knapSackRec(int W, int[] wt, int[] val,
                           int n, int[, ] dp)
    {
 
        // Base condition
        if (n == 0 || W == 0)
            return 0;
        if (dp[n, W] != -1)
            return dp[n, W];
        if (wt[n - 1] > W)
 
            // Store the value of function call
            // stack in table before return
            return dp[n, W]
                = knapSackRec(W, wt, val, n - 1, dp);
 
        else
 
            // Return value of table after storing
            return dp[n, W]
                = max((val[n - 1]
                       + knapSackRec(W - wt[n - 1], wt, val,
                                     n - 1, dp)),
                      knapSackRec(W, wt, val, n - 1, dp));
    }
 
    static int knapSack(int W, int[] wt, int[] val, int N)
    {
 
        // Declare the table dynamically
        int[, ] dp = new int[N + 1, W + 1];
 
        // Loop to initially filled the
        // table with -1
        for (int i = 0; i < N + 1; i++)
            for (int j = 0; j < W + 1; j++)
                dp[i, j] = -1;
 
        return knapSackRec(W, wt, val, N, dp);
    }
 
    // Driver Code
    static public void Main()
    {
 
        int[] val = new int[]{ 60, 100, 120 };
        int[] wt = new int[]{ 10, 20, 30 };
 
        int W = 50;
        int N = val.Length;
 
        Console.WriteLine(knapSack(W, wt, val, N));
    }
}
 
// This Code is contributed By Dharanendra L V.

Javascript

<script>
// A utility function that returns
// maximum of two integers   
function max(a,  b)   
{   
    return (a > b) ? a : b;   
}
 
// Returns the value of maximum profit
function knapSackRec(W, wt, val, n,dp)
{
     
    // Base condition
    if (n == 0 || W == 0)
        return 0;
         
    if (dp[n][W] != -1)
        return dp[n][W];
     
    if (wt[n - 1] > W)
     
        // Store the value of function call
        // stack in table before return
        return dp[n][W] = knapSackRec(W, wt, val,
                                    n - 1, dp);
                                     
    else
     
        // Return value of table after storing
        return dp[n][W] = max((val[n - 1] +
                            knapSackRec(W - wt[n - 1], wt,
                                        val, n - 1, dp)),
                            knapSackRec(W, wt, val,
                                        n - 1, dp));           
}
 
function knapSack( W, wt,val,N)
{
     
    // Declare the table dynamically
    var dp = new Array(N + 1);
    for(var i = 0; i < dp.length; i++)
    {
        dp[i]=new Array(W + 1);
      }
     
    // Loop to initially filled the
    // table with -1
    for(var i = 0; i < N + 1; i++)
        for(var j = 0; j < W + 1; j++)
            dp[i][j] = -1;
     
    return knapSackRec(W, wt, val, N, dp);   
}
 
 
   var val= [ 60, 100, 120 ];
    var wt = [ 10, 20, 30 ];
     
    var W = 50;
    var N = val.length;       
     
    document.write(knapSack(W, wt, val, N));
 
// This code is contributed by akshitsaxenaa09.
 
</script>

C++

#include <bits/stdc++.h>
using namespace std;
int knapSack(int W, int wt[], int val[], int n)
{
    // making and initializing dp array
    int dp[W + 1];
    memset(dp, 0, sizeof(dp));
 
    for (int i = 1; i < n + 1; i++) {
        for (int w = W; w >= 0; w--) {
 
            if (wt[i - 1] <= w)
                // finding the maximum value
                dp[w] = max(dp[w],
                            dp[w - wt[i - 1]] + val[i - 1]);
        }
    }
    return dp[W]; // returning the maximum value of knapsack
}
int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    cout << knapSack(W, wt, val, n);
    return 0;
}

Java

import java.util.*;
 
class GFG{
  static int knapSack(int W, int wt[], int val[], int n)
  {
    // making and initializing dp array
    int []dp = new int[W + 1];
 
 
    for (int i = 1; i < n + 1; i++) {
      for (int w = W; w >= 0; w--) {
 
        if (wt[i - 1] <= w)
           
          // finding the maximum value
          dp[w] = Math.max(dp[w],
                           dp[w - wt[i - 1]] + val[i - 1]);
      }
    }
    return dp[W]; // returning the maximum value of knapsack
  }
   
  // Driver code
  public static void main(String[] args)
  {
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = val.length;
    System.out.print(knapSack(W, wt, val, n));
  }
}
 
// This code is contributed by gauravrajput1

Python3

# code
# A Dynamic Programming based Python
# Program for 0-1 Knapsack problem
# Returns the maximum value that can
# be put in a knapsack of capacity W
 
 
def knapSack(W, wt, val, n):
    dp = [0 for i in range(W+1)]  # Making the dp array
 
    for i in range(1, n+1):  # taking first i elements
        for w in range(W, 0, -1):  # starting from back,so that we also have data of
                                # previous computation when taking i-1 items
            if wt[i-1] <= w:
                # finding the maximum value
                dp[w] = max(dp[w], dp[w-wt[i-1]]+val[i-1])
 
    return dp[W]  # returning the maximum value of knapsack
 
 
# Driver code
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
# This code is contributed by Suyash Saxena
print(knapSack(W, wt, val, n))

C#

using System;
public class GFG {
    static int knapSack(int W, int []wt, int []val, int n)
    {
       
        // making and initializing dp array
        int[] dp = new int[W + 1];
 
        for (int i = 1; i < n + 1; i++)
        {
            for (int w = W; w >= 0; w--)
            {
 
                if (wt[i - 1] <= w)
 
                    // finding the maximum value
                    dp[w] = Math.Max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);
            }
        }
        return dp[W]; // returning the maximum value of knapsack
    }
 
    // Driver code
    public static void Main(String[] args) {
        int []val = { 60, 100, 120 };
        int []wt = { 10, 20, 30 };
        int W = 50;
        int n = val.Length;
        Console.Write(knapSack(W, wt, val, n));
    }
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
    function knapSack(W , wt , val , n)
    {
     
        // making and initializing dp array
        var dp = Array(W + 1).fill(0);
 
        for (i = 1; i < n + 1; i++) {
            for (w = W; w >= 0; w--) {
 
                if (wt[i - 1] <= w)
 
                    // finding the maximum value
                    dp[w] = Math.max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);
            }
        }
        return dp[W]; // returning the maximum value of knapsack
    }
 
    // Driver code
        var val = [ 60, 100, 120 ];
        var wt = [ 10, 20, 30 ];
        var W = 50;
        var n = val.length;
        document.write(knapSack(W, wt, val, n));
 
// This code is contributed by Rajput-Ji
</script>

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 *