Bài toán cái túi (knapsack) trong java

Lập trình Java

Bài toán cái túi (hay còn gọi là bài toán knapsack) là một bài toán tối ưu hóa về cách sắp xếp các đồ vật vào trong một cái túi để giá trị tổng của chúng là lớn nhất. Trong bài toán này, mỗi đồ vật có giá trị và khối lượng riêng, cần phải chọn ra một tập hợp các đồ vật sao cho tổng khối lượng chúng không vượt quá giới hạn của cái túi và tổng giá trị là lớn nhất.

Ví dụ, giả sử có một cái túi có khả năng chứa tối đa 50 đơn vị khối lượng và có các đồ vật sau:

Đồ vật Giá trị Khối lượng
A 60 10
B 100 20
C 120 30

Thuật toán dynamic programming là một trong những thuật toán phổ biến để giải quyết bài toán cái túi. Nó được áp dụng bằng cách tạo bảng giá trị tối ưu cho các trường hợp con của bài toán, từ đó tính toán giá trị tối ưu cho trường hợp lớn hơn.

Dưới đây là một ví dụ về thuật toán dynamic programming để giải quyết bài toán cái túi trong Java:

public class Knapsack {
    public static int knapsack(int W, int wt[], int val[], int n) {
        int[][] K = new int[n + 1][W + 1];
 
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    K[i][w] = 0;
                else if (wt[i - 1] <= w)
                    K[i][w] = Math.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) {
        int val[] = new int[] { 60, 100, 120 };
        int wt[] = new int[] { 10, 20, 30 };
        int W = 50;
        int n = val.length;
        System.out.println(knapsack(W, wt, val, n));
    }
}

Ngoài giải thuật trên, chúng ta có thể sử dụng Thuật toán quay lui. Để giải bài toán cái túi sử dụng thuật toán quay lui, chúng ta có thể làm như sau:

  1. Xác định số lượng vật phẩm cần đưa vào túi.
  2. Khởi tạo một mảng boolean để lưu trạng thái của vật phẩm có nằm trong túi hay không.
  3. Tính toán giá trị tối đa của túi và khởi tạo biến lưu giá trị tối đa ban đầu là 0.
  4. Bắt đầu quá trình quay lui từ vật phẩm đầu tiên đến vật phẩm cuối cùng: a. Nếu vật phẩm chưa được chọn và trọng lượng của túi cộng với trọng lượng của vật phẩm đó nhỏ hơn hoặc bằng khối lượng tối đa của túi, đánh dấu vật phẩm này là đã được chọn và cộng giá trị của nó vào giá trị hiện tại của túi. b. Tiếp tục đệ quy với các vật phẩm tiếp theo. c. Nếu giá trị hiện tại của túi lớn hơn giá trị tối đa, lưu lại giá trị hiện tại làm giá trị tối đa. d. Bỏ đánh dấu vật phẩm đã được chọn và thử với các vật phẩm khác.
  5. Trả về giá trị tối đa của túi.

Dưới đây là một đoạn mã minh họa cho giải pháp này:

public class Knapsack {
    private int capacity;
    private int[] weights;
    private int[] values;
    private boolean[] solution;

    public Knapsack(int capacity, int[] weights, int[] values) {
        this.capacity = capacity;
        this.weights = weights;
        this.values = values;
        this.solution = new boolean[weights.length];
    }

    public int solve() {
        return solveRecursively(0, 0, 0);
    }

    private int solveRecursively(int index, int weight, int value) {
        if (index == weights.length) {
            return value;
        }

        // Do not choose the item
        int result = solveRecursively(index + 1, weight, value);

        // Choose the item if it fits
        if (weight + weights[index] <= capacity) {
            solution[index] = true;
            result = Math.max(result, solveRecursively(index + 1, weight + weights[index], value + values[index]));
            solution[index] = false;
        }

        return result;
    }

    public static void main(String[] args) {
        int capacity = 50;
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};

        Knapsack knapsack = new Knapsack(capacity, weights, values);
        int maxValue = knapsack.solve();
        System.out.println("Max value: " + maxValue);
    }
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *