编辑代码

import java.util.*;

public class Knapsack {
    public static void main(String[] args) {
        int max_time = 4;
        Attraction[] attractions = {new Attraction("故宫", 1, 7), new Attraction("颐和园", 2, 8), new Attraction("长城", 3, 9), new Attraction("天坛", 1, 6)};
        int num_attractions = attractions.length;
        int[] weights = new int[num_attractions];
        int[] values = new int[num_attractions];

        for (int i = 0; i < num_attractions; i++) {
            weights[i] = attractions[i].time;
            values[i] = attractions[i].rating;
        }

        List<Integer> selected = knapsack(max_time, weights, values, num_attractions);
        System.out.println("以下是您可以获得的最大价值的景点：");
        for (int i = 0; i < selected.size(); i++) {
            System.out.println((i + 1) + ". " + attractions[selected.get(i)].name);
        }
    }

    public static List<Integer> knapsack(int max_time, int[] weights, int[] values, int num_attractions) {
        int[][] dp = new int[num_attractions + 1][max_time + 1];

        for (int i = 1; i <= num_attractions; i++) {
            for (int w = 1; w <= max_time; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        int res = dp[num_attractions][max_time];
        int w = max_time;
        List<Integer> selected = new ArrayList<>();

        for (int i = num_attractions; i > 0 && res > 0; i--) {
            if (res == dp[i - 1][w]) {
                continue;
            } else {
                selected.add(i - 1);
                res -= values[i - 1];
                w -= weights[i - 1];
            }
        }

        return selected;
    }
}