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