Future Vision BIE Future Vision BIE


ONE STOP FOR ALL STUDY MATERIALS & LAB PROGRAMS


E MENU Whatsapp Share Join Telegram, to get Instant Updates
× NOTE! Click on MENU to Browse between Subjects...
Advertisement

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY

(Effective from the academic year 2018 -2019)

SEMESTER - IV

Course Code 18CSL47

CIE Marks 40

Number of Contact Hours/Week 0:2:2

SEE Marks 60

Total Number of Lab Contact Hours 36

Exam Hours 03



Advertisement

Experiments 6 A

Implement in Java, the 0/1 Knapsack problem using
(a) Dynamic Programming method



Download the Source Code 6 A
Advertisement 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.Scanner;

class Knapsack {
    int[] weight, profit;
    int capacity, n;

    Knapsack() {		//constructor automatically called
        Scanner scan = new Scanner(System.in);

        System.out.println("Enter Number of Items");
        n = scan.nextInt();
        weight = new int[n];
        profit = new int[n];

        System.out.println("Enter Weights of Items");
        for (int i = 0; i < n; i++) {
            weight[i] = scan.nextInt();
        }

        System.out.println("Enter Profits of Items");
        for (int i = 0; i < n; i++) {
            profit[i] = scan.nextInt();
        }

        System.out.println("Enter Capacity of Knapsack");
        capacity = scan.nextInt();
        scan.close();
    }

    void fill() {
        int[][] K = new int[n + 1][capacity + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= capacity; j++) {
                if (i == 0 || j == 0) {
                    K[i][j] = 0;
                } else if (j < weight[i - 1]) {
                    K[i][j] = K[i - 1][j];
                } else {
                    K[i][j] = Math.max(K[i - 1][j], profit[i - 1] + K[i - 1][j - weight[i - 1]]);
                }
            }
        }
        System.out.println("Maximum Profit: " + (K[n][capacity]));

        System.out.print("Items Considered: ");

        int i = n, j = capacity;

        while (i > 0 && j > 0) {
            if (K[i][j] != K[i - 1][j]) {
                System.out.print(i + " ");
                j -= weight[i - 1];
            }
            i -= 1;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Knapsack knapsack = new Knapsack();
        knapsack.fill();
    }
}

output
Fig 6 A: Output .

Advertisement

Experiments 6 B

Implement in Java, the 0/1 Knapsack problem using
(b) Greedy method.



Advertisement
Download the Source Code 6 B
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.Scanner;

class Knapsack {

    double[] weight, profit, ratio, solnVector;
    double capacity;

    Knapsack() {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter number of Items");
        int n = scan.nextInt();
        weight = new double[n];
        profit = new double[n];
        ratio = new double[n];
        solnVector = new double[n];

        System.out.println("Enter Weights of Items");
        for (int i = 0; i < n; i++) {
            weight[i] = scan.nextDouble();
        }

        System.out.println("Enter Profits of Items");
        for (int i = 0; i < n; i++) {
            profit[i] = scan.nextDouble();
        }

        System.out.println("Enter Capacity of Knapsack");
        capacity = scan.nextDouble();
        scan.close();
    }

    int getNext() {
        int index = -1;
        double highest = 0;

        for (int i = 0; i < ratio.length; i++) {
            if (ratio[i] > highest) {
                highest = ratio[i];
                index = i;
            }
        }
        return index;
    }

    void fill() {
        double currentWeight = 0;
        double currentProfit = 0;
        
        for (int i = 0; i < ratio.length; i++) {
            ratio[i] = profit[i] / weight[i];
        }

        System.out.print("Items Considered: ");
        while (currentWeight < capacity) {
            int item = getNext();

            if (item == -1) {
                break;
            }

            System.out.print((item + 1) + " ");

            if (currentWeight + weight[item] <= capacity) {
                currentWeight += weight[item];
                currentProfit += profit[item];
                solnVector[item] = 1;
                ratio[item] = 0;
            } else {
                currentProfit += ratio[item] * (capacity - currentWeight);
                solnVector[item] = (capacity - currentWeight) / weight[item];
                break;
            }
        }

        System.out.println();
        System.out.println("Maximum Profit is: " + currentProfit);
        System.out.print("Solution Vector: ");
        for (int i = 0; i < solnVector.length; i++) {
            System.out.print(solnVector[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Knapsack knapsack = new Knapsack();
        knapsack.fill();
    }
}
Advertisement
output
Fig 6 B: Output .

× Note Please Share the website link with Your Friends and known Students...

-ADMIN

× Note Page Number is specified to navigate between Pages...
T = Text book
QB = Question Bank
AS = Amswer Script

-ADMIN
Advertisement