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).
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