algorithm - 解分数背包的方法

Question

我必须实现两种算法来解决 fractional knapsack ，但直到现在我才发现并实现了贪婪的方法。

我搜索了很多其他算法(如动态规划，我读过它也可以解决分数背包问题，但我找不到任何伪代码)。我找到的所有东西都是大约 0/1 个背包。

有没有人有可以解决分数背包的链接或任何算法？

Answer 1

@yola21 在 java 代码中的回答:
自己定义未定义的函数，它们是关于接受用户输入的。

//define your variables here 


        System.out.println("Enter number of items:");
        size = acceptNumberOfItems()

        System.out.println("Enter size of your knapsack:");
        size = acceptKnapsackSize()

        System.out.println("Enter weight of each item:");

        acceptWeightArray(weight)

        System.out.println("Enter value of each item:");

        acceptWeightArray(value)

        double[][] valuePerWeight = new double[size][2];

        double maxValue = 0;

        for(int i=0; i<size; ++i){
            valuePerWeight[i][0] = value[i]/weight[i];
            valuePerWeight[i][1] = weight[i];
        }

        java.util.Arrays.sort(valuePerWeight, new java.util.Comparator<double[]>() {
                    public int compare(double[] a, double[] b) {
                        return Double.compare(a[0], b[0]);
                    }
                });



        int i = size-1;
        while(knapsackSize > 0  && size >0){
            //while not full

            if(valuePerWeight[i][1] > knapsackSize){
                maxValue += knapsackSize * valuePerWeight[i][0];
                knapsackSize = 0;
            }
            else{

                maxValue +=  valuePerWeight[i][1] * valuePerWeight[i][0];
                knapsackSize -= valuePerWeight[i][1];
            }


            --i;
        }
        System.out.println("Max Value:" + maxValue);
    }