Mochila fraccional ilimitada

Dados los pesos y valores de n artículos, la tarea es poner estos artículos en una mochila de capacidad W para obtener el máximo valor total en la mochila, podemos poner repetidamente el mismo artículo y también podemos poner una fracción de un artículo.

Ejemplos:  

Entrada: val[] = {14, 27, 44, 19}, wt[] = {6, 7, 9, 8}, W = 50 
Salida: 244.444

Entrada: val[] = {100, 60, 120}, wt[] = {20, 10, 30}, W = 50 
Salida: 300 

Enfoque: La idea aquí es simplemente encontrar el artículo que tiene la mayor relación valor / peso . Luego llene toda la mochila solo con este artículo, para maximizar el valor final de la mochila.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum required value
float knapSack(int W, float wt[], float val[], int n)
{
 
    // maxratio will store the maximum value to weight
    // ratio we can have for any item and maxindex
    // will store the index of that element
    float maxratio = INT_MIN;
    int maxindex = 0;
 
    // Find the maximum ratio
    for (int i = 0; i < n; i++) {
        if ((val[i] / wt[i]) > maxratio) {
            maxratio = (val[i] / wt[i]);
            maxindex = i;
        }
    }
 
    // The item with the maximum value to
    // weight ratio will be put into
    // the knapsack repeatedly until full
    return (W * maxratio);
}
 
// Driver code
int main()
{
    float val[] = { 14, 27, 44, 19 };
    float wt[] = { 6, 7, 9, 8 };
    int n = sizeof(val) / sizeof(val[0]);
    int W = 50;
 
    cout << knapSack(W, wt, val, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
    // Function to return the maximum required value
    static float knapSack(int W, float wt[],
                            float val[], int n)
    {
 
        // maxratio will store the maximum value to weight
        // ratio we can have for any item and maxindex
        // will store the index of that element
        float maxratio = Integer.MIN_VALUE;
        int maxindex = 0;
 
        // Find the maximum ratio
        for (int i = 0; i < n; i++)
        {
            if ((val[i] / wt[i]) > maxratio)
            {
                maxratio = (val[i] / wt[i]);
                maxindex = i;
            }
        }
 
        // The item with the maximum value to
        // weight ratio will be put into
        // the knapsack repeatedly until full
        return (W * maxratio);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        float val[] = {14, 27, 44, 19};
        float wt[] = {6, 7, 9, 8};
        int n = val.length;
        int W = 50;
 
        System.out.println(knapSack(W, wt, val, n));
    }
}
 
// This code is contributed by 29AjayKumar

# Python implementation of the approach
 
import sys
 
# Function to return the maximum required value
def knapSack(W, wt, val, n):
 
    # maxratio will store the maximum value to weight
    # ratio we can have for any item and maxindex
    # will store the index of that element
    maxratio = -sys.maxsize-1;
    maxindex = 0;
 
    # Find the maximum ratio
    for i in range(n):
        if ((val[i] / wt[i]) > maxratio):
            maxratio = (val[i] / wt[i]);
            maxindex = i;
 
 
    # The item with the maximum value to
    # weight ratio will be put into
    # the knapsack repeatedly until full
    return (W * maxratio);
 
 
# Driver code
 
val = [ 14, 27, 44, 19 ];
wt = [ 6, 7, 9, 8 ];
n = len(val);
W = 50;
 
print(knapSack(W, wt, val, n));
 
# This code is contributed by Rajput-Ji

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the maximum required value
    static float knapSack(int W, float []wt,
                            float []val, int n)
    {
 
        // maxratio will store the maximum value to weight
        // ratio we can have for any item and maxindex
        // will store the index of that element
        float maxratio = int.MinValue;
        int maxindex = 0;
 
        // Find the maximum ratio
        for (int i = 0; i < n; i++)
        {
            if ((val[i] / wt[i]) > maxratio)
            {
                maxratio = (val[i] / wt[i]);
                maxindex = i;
            }
        }
 
        // The item with the maximum value to
        // weight ratio will be put into
        // the knapsack repeatedly until full
        return (W * maxratio);
    }
 
    // Driver code
    public static void Main()
    {
        float []val = {14, 27, 44, 19};
        float []wt = {6, 7, 9, 8};
        int n = val.Length;
        int W = 50;
 
        Console.WriteLine(knapSack(W, wt, val, n));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the approach
 
// Function to return the maximum required value
function knapSack(W, wt, val, n)
{
 
    // maxratio will store the maximum value to weight
    // ratio we can have for any item and maxindex
    // will store the index of that element
    var maxratio = -1000000000;
    var maxindex = 0;
 
    // Find the maximum ratio
    for (var i = 0; i < n; i++) {
        if (parseInt(val[i] / wt[i]) > maxratio) {
            maxratio = (val[i] / wt[i]);
            maxindex = i;
        }
    }
 
    // The item with the maximum value to
    // weight ratio will be put into
    // the knapsack repeatedly until full
    return (W * maxratio);
}
 
// Driver code
var val = [14, 27, 44, 19];
var wt = [6, 7, 9, 8];
var n = val.length;
var W = 50;
document.write( knapSack(W, wt, val, n).toFixed(3));
 
</script>

244.444