knasack

 knapsack

import java.util.ArrayList;
import java.util.List;

public class KnapsackDP {

   
    public static int knapsack(int[] values, int[] weights, int capacity) {
        int n = values.length;
        int[][] dp = new int[n + 1][capacity + 1];

        // Build dp table
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

       
        List<Integer> selectedItems = new ArrayList<>();
        int w = capacity;
        for (int i = n; i > 0; i--) {
            if (dp[i][w] != dp[i - 1][w]) {
                selectedItems.add(i - 1); // Add item index
                w -= weights[i - 1]; // Reduce remaining capacity
            }
        }

       
        System.out.println("Selected item indices: " + selectedItems);
        return dp[n][capacity]; // The maximum value is in dp[n][capacity]
    }

    public static void main(String[] args) {
       
        int[] values = {10,10,12,18};
        int[] weights = {2,4,6,9};
        int capacity = 4;

       
        int maxValue = knapsack(values, weights, capacity);

       
        System.out.println("Maximum Value: " + maxValue);
    }
}









Comments

Post a Comment

Popular posts from this blog

q3part b

  import java . util . Random ; public class TSPMutation {     public static void main( String [] args ) {         // Example cities (0, 1, 2, 3, 4)         int [] chromosome = { 0 , 1 , 2 , 3 , 4 }; // A possible solution (tour)                 System .out.println( "Original Chromosome:" );         printChromosome(chromosome);                 // Apply Mutation (Swap two cities in the path)         mutate(chromosome);                 System .out.println( "Mutated Chromosome:" );         printChromosome(chromosome);     }     // Mutation function: Swap two cities' positions     public static void mutate( int [] chromosome ) {         Random rand = new Random();           ...
Read more

Literal table

 #code import java.util.*; class Literal {     String value;     int address;     public Literal(String value) {         this.value = value;         this.address = -1; // not assigned yet     } } public class Ass2{     // Check if a literal already exists in the list     public static boolean literalExists(List<Literal> list, String value) {         for (Literal l : list) {             if (l.value.equals(value)) return true;         }         return false;     }     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         List<String> code = new ArrayList<>();         List<Literal> literalTable = new ArrayList<>();         Lis...
Read more

quicksort 1

 import java.util.Random; public class QuicksortExample {     public static void main(String[] args) {         int N = 500; // Number of elements to sort         // Initialize an array of random integers         int[] arr = new int[N];         Random rand = new Random();         for (int i = 0; i < N; i++) {             arr[i] = rand.nextInt(1000); // Random integers between 0 and 999         }         // Displaying the unsorted array (optional)         System.out.println("Unsorted array:");         printArray(arr);         // Start measuring time         long startTime = System.nanoTime();         // Call the quicksort method         quicksort(arr, 0, N - 1);       ...
Read more