Как найти максимальное среднее и минимальное значение в задаче о рюкзаке - PullRequest
Новая
       70

Как найти максимальное среднее и минимальное значение в задаче о рюкзаке

0 голосов
/ 17 июня 2020
  1. Наша корзина будет выдерживать вес 1000. Используя генератор случайных чисел, сгенерируйте 100 возможных предметов для корзины. Элементы должны иметь случайный вес от 1 до 300.
  2. Используйте алгоритм программирования Dynami c, чтобы вычислить точное оптимальное решение для набора из 100 элементов. Обратите внимание, что решение представляет собой вес, wj, где 0
  3. Используйте алгоритм жадного приближения для вычисления приближенного решения с использованием того же набора элементов.
  4. Выполните этот набор шагов 10 раз, отслеживая высокие, низкие и средние значения. Также следите за временем работы обоих алгоритмов.

Этот проект требует отслеживания высоких, низких и средних значений и должен содержать таблицу с вашими экспериментальными результатами: 

    Dynamic(Exact)  Greedy(Approx.) Approximation Factor

Самый высокий
Средний
Самый низкий 

package knapsack;
import java.util.Random;

/**
 *
 * @author Muhammad Ali Ghaffar
 */
public class Knapsack {

    public int max(int a, int b){
        return (a > b) ? a : b;
    }

    public int min(int a, int b){
        return (a < b) ? a : b;
    }


    public int KSKMAX(int W, int wt[], int val[], int n) 
    { 
        int i, w; 
        int K[][] = new int[n + 1][W + 1]; 

        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]; 
    }



    public static void main(String[] args) {
        // TODO code application logic here
        Knapsack k1=new Knapsack();
        Random rand = new Random();

        int randomvalues = rand.nextInt(100);

        int val[] = new int[100]; 
        int wt[] = new int[1000]; 

        for(int i=0;i<100;i++){
            val[i]=rand.nextInt(100)+1;

        }



        int W = rand.nextInt(300); 
        int n = val.length;
        System.out.println("----------------");
        System.out.println("| Highest :"+k1.KSKMAX(W, wt, val, n)+"  |");
        System.out.println("----------------");
        System.out.println("| Average :"+k1.KSKMAX(W, wt, val, n)+"  |");
        System.out.println("----------------");
        System.out.println("| Lowest  :"+k1.KSKLOW(W, wt, val, n)+"  |");
        System.out.println("----------------");

    }

}
...