Dados los pesos y valores de N artículos y la capacidad W de la mochila. También dado que el peso de como máximo K elementos se puede cambiar a la mitad de su peso original. La tarea es encontrar la suma máxima de valores de N elementos que se pueden obtener de modo que la suma de los pesos de los elementos en la mochila no exceda la capacidad W dada .
Ejemplos:
Entrada: W = 4, K = 1, valor = [17, 20, 10, 15], peso = [4, 2, 7, 5]
Salida: 37
Explicación: Cambie el peso de como máximo K elementos a la mitad del peso de una manera óptima para obtener el máximo valor. Disminuya el peso del primer elemento a la mitad y agregue el peso del segundo elemento. La suma resultante del valor es 37, que es el máximo.Entrada: W = 8, K = 2, valor = [17, 20, 10, 15], peso = [4, 2, 7, 5]
Salida: 53
Explicación: Cambie el peso del último artículo y el primer artículo y el agregue el peso del segundo artículo, el valor total de la suma del artículo será 53.
Planteamiento: El problema dado es la variación del problema de la mochila 0 1 . La bandera indica el número de artículos cuyo peso se ha reducido a la mitad. En cada llamada recursiva se calcula y devuelve un máximo de los siguientes casos:
- Caso base: si el índice excede la longitud de los valores, devuelve cero
- Si la bandera es igual a K, se considera un máximo de 2 casos:
- Incluir artículo con peso completo si el peso del artículo no excede el peso restante
- Saltar el elemento
- Si la bandera es menor que K, se considera un máximo de 3 casos:
- Incluir artículo con peso completo si el peso del artículo no excede el peso restante
- Incluya el artículo con la mitad del peso si la mitad del peso del artículo no excede el peso restante
- Saltar el elemento
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum value
int maximum(int value[],
int weight[], int weight1,
int flag, int K, int index, int val_len)
{
// base condition
if (index >= val_len)
{
return 0;
}
// K elements already reduced
// to half of their weight
if (flag == K)
{
// Dont include item
int skip = maximum(value,
weight, weight1,
flag, K, index + 1, val_len);
int full = 0;
// If weight of the item is
// less than or equal to the
// remaining weight then include
// the item
if (weight[index] <= weight1)
{
full = value[index] + maximum(
value, weight,
weight1 - weight[index], flag,
K, index + 1, val_len);
}
// Return the maximum of
// both cases
return max(full, skip);
}
// If the weight reduction to half
// is possible
else
{
// Skip the item
int skip = maximum(
value, weight,
weight1, flag,
K, index + 1, val_len);
int full = 0;
int half = 0;
// Include item with full weight
// if weight of the item is less
// than the remaining weight
if (weight[index] <= weight1)
{
full = value[index] + maximum(
value, weight,
weight1 - weight[index],
flag, K, index + 1, val_len);
}
// Include item with half weight
// if half weight of the item is
// less than the remaining weight
if (weight[index] / 2 <= weight1)
{
half = value[index] + maximum(
value, weight,
weight1 - weight[index] / 2,
flag, K, index + 1, val_len);
}
// Return the maximum of all 3 cases
return max(full,
max(skip, half));
}
}
int main()
{
int value[] = {17, 20, 10, 15};
int weight[] = {4, 2, 7, 5};
int K = 1;
int W = 4;
int val_len = sizeof(value) / sizeof(value[0]);
cout << (maximum(value, weight, W,
0, K, 0, val_len));
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the maximum value
static int maximum(int value[],
int weight[], int weight1,
int flag, int K, int index)
{
// base condition
if (index >= value.length) {
return 0;
}
// K elements already reduced
// to half of their weight
if (flag == K) {
// Dont include item
int skip = maximum(value,
weight, weight1,
flag, K, index + 1);
int full = 0;
// If weight of the item is
// less than or equal to the
// remaining weight then include
// the item
if (weight[index] <= weight1) {
full = value[index]
+ maximum(
value, weight,
weight1 - weight[index], flag,
K, index + 1);
}
// Return the maximum of
// both cases
return Math.max(full, skip);
}
// If the weight reduction to half
// is possible
else {
// Skip the item
int skip = maximum(
value, weight,
weight1, flag,
K, index + 1);
int full = 0;
int half = 0;
// Include item with full weight
// if weight of the item is less
// than the remaining weight
if (weight[index] <= weight1) {
full = value[index]
+ maximum(
value, weight,
weight1 - weight[index],
flag, K, index + 1);
}
// Include item with half weight
// if half weight of the item is
// less than the remaining weight
if (weight[index] / 2 <= weight1) {
half = value[index]
+ maximum(
value, weight,
weight1 - weight[index] / 2,
flag, K, index + 1);
}
// Return the maximum of all 3 cases
return Math.max(full,
Math.max(skip, half));
}
}
public static void main(String[] args)
throws Exception
{
int value[] = { 17, 20, 10, 15 };
int weight[] = { 4, 2, 7, 5 };
int K = 1;
int W = 4;
System.out.println(
maximum(value, weight, W,
0, K, 0));
}
}
Python3
# Python program for the above approach # Function to find the maximum value def maximum(value, weight, weight1, flag, K, index, val_len) : # base condition if (index >= val_len) : return 0 # K elements already reduced # to half of their weight if (flag == K) : # Dont include item skip = maximum(value, weight, weight1, flag, K, index + 1, val_len) full = 0 # If weight of the item is # less than or equal to the # remaining weight then include # the item if (weight[index] <= weight1) : full = value[index] + maximum( value, weight, weight1 - weight[index], flag, K, index + 1, val_len) # Return the maximum of # both cases return max(full, skip) # If the weight reduction to half # is possible else : # Skip the item skip = maximum( value, weight, weight1, flag, K, index + 1, val_len) full = 0 half = 0 # Include item with full weight # if weight of the item is less # than the remaining weight if (weight[index] <= weight1) : full = value[index] + maximum( value, weight, weight1 - weight[index], flag, K, index + 1, val_len) # Include item with half weight # if half weight of the item is # less than the remaining weight if (weight[index] / 2 <= weight1) : half = value[index] + maximum( value, weight, weight1 - weight[index] / 2, flag, K, index + 1, val_len) # Return the maximum of all 3 cases return max(full, max(skip, half)) # Driver Code value = [ 17, 20, 10, 15 ] weight = [ 4, 2, 7, 5 ] K = 1 W = 4 val_len = len(value) print(maximum(value, weight, W, 0, K, 0, val_len)) # This code is contributed by sanjoy_62.
C#
// C# implementation for the above approach
using System;
public class GFG {
// Function to find the maximum value
static int maximum(int []value,
int []weight, int weight1,
int flag, int K, int index)
{
// base condition
if (index >= value.Length) {
return 0;
}
// K elements already reduced
// to half of their weight
if (flag == K) {
// Dont include item
int skip = maximum(value,
weight, weight1,
flag, K, index + 1);
int full = 0;
// If weight of the item is
// less than or equal to the
// remaining weight then include
// the item
if (weight[index] <= weight1) {
full = value[index]
+ maximum(
value, weight,
weight1 - weight[index], flag,
K, index + 1);
}
// Return the maximum of
// both cases
return Math.Max(full, skip);
}
// If the weight reduction to half
// is possible
else {
// Skip the item
int skip = maximum(
value, weight,
weight1, flag,
K, index + 1);
int full = 0;
int half = 0;
// Include item with full weight
// if weight of the item is less
// than the remaining weight
if (weight[index] <= weight1) {
full = value[index]
+ maximum(
value, weight,
weight1 - weight[index],
flag, K, index + 1);
}
// Include item with half weight
// if half weight of the item is
// less than the remaining weight
if (weight[index] / 2 <= weight1) {
half = value[index]
+ maximum(
value, weight,
weight1 - weight[index] / 2,
flag, K, index + 1);
}
// Return the maximum of all 3 cases
return Math.Max(full,
Math.Max(skip, half));
}
}
// Driver code
public static void Main(String[] args)
{
int []value = { 17, 20, 10, 15 };
int []weight = { 4, 2, 7, 5 };
int K = 1;
int W = 4;
Console.WriteLine(
maximum(value, weight, W,
0, K, 0));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript implementation for the above approach
// Function to find the maximum value
function maximum(value,
weight , weight1,
flag , K , index)
{
// base condition
if (index >= value.length) {
return 0;
}
// K elements already reduced
// to half of their weight
if (flag == K) {
// Dont include item
var skip = maximum(value,
weight, weight1,
flag, K, index + 1);
var full = 0;
// If weight of the item is
// less than or equal to the
// remaining weight then include
// the item
if (weight[index] <= weight1) {
full = value[index]
+ maximum(
value, weight,
weight1 - weight[index], flag,
K, index + 1);
}
// Return the maximum of
// both cases
return Math.max(full, skip);
}
// If the weight reduction to half
// is possible
else {
// Skip the item
var skip = maximum(
value, weight,
weight1, flag,
K, index + 1);
var full = 0;
var half = 0;
// Include item with full weight
// if weight of the item is less
// than the remaining weight
if (weight[index] <= weight1) {
full = value[index]
+ maximum(
value, weight,
weight1 - weight[index],
flag, K, index + 1);
}
// Include item with half weight
// if half weight of the item is
// less than the remaining weight
if (weight[index] / 2 <= weight1) {
half = value[index]
+ maximum(
value, weight,
weight1 - weight[index] / 2,
flag, K, index + 1);
}
// Return the maximum of all 3 cases
return Math.max(full,
Math.max(skip, half));
}
}
// Driver code
var value = [ 17, 20, 10, 15 ];
var weight = [ 4, 2, 7, 5 ];
var K = 1;
var W = 4;
document.write(
maximum(value, weight, W,
0, K, 0));
// This code is contributed by Princi Singh
</script>
Producción
37
Complejidad de tiempo: O(3^N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA