快捷導(dǎo)航

java解析背包問題實(shí)例代碼(簡單易懂)

更新時間：2025年10月09日 08:29:46 作者：王超林WCL

背包問題是計(jì)算機(jī)科學(xué)中的經(jīng)典問題,涉及到在給定的一組物品中選擇最佳的物品組合,以使其總重量不超過背包所能承載的限制,同時獲得最大的總價值,這篇文章主要介紹了java解析背包問題的相關(guān)資料,需要的朋友可以參考下

問題場景‌：

國慶出去玩，行李箱只能裝5公斤，但你想帶：

單反相機(jī)（3kg，拍照必備）
燒水壺（1kg，喝熱水方便）
5件衣服（5kg，每天換著穿）
充電寶（0.5kg，手機(jī)沒電會焦慮）

‌問：怎么裝才能既不超過重量，又讓旅行最舒服？

1. 核心思想‌

用一個表格（叫dp）記錄不同重量能裝的最大價值。比如：

表格行：物品（相機(jī)、燒水壺...）

表格列：行李箱剩余容量（0kg~5kg）

填表規(guī)則：‌每次決定裝不裝當(dāng)前物品‌，選價值更高的方案。

2. 直接上代碼‌

public class PackingHelper {
    public static void main(String[] args) {
        int maxWeight = 5; // 行李箱限重5kg
        double[] weights = {3, 1, 5, 0.5}; // 每個物品的重量
        int[] values = {10, 4, 7, 3};     // 物品的重要性打分（自己設(shè)定）

        // 開始填表
        int[][] dp = new int[weights.length + 1][maxWeight + 1];
        for (int i = 1; i <= weights.length; i++) {
            for (int w = 0; w <= maxWeight; w++) {
                if (weights[i - 1] <= w) {
                    // 能裝下時：比較"裝"和"不裝"哪個更劃算
                    dp[i][w] = Math.max(
                        dp[i - 1][w], // 不裝
                        dp[i - 1][w - (int) weights[i - 1]] + values[i - 1] // 裝
                    );
                } else {
                    dp[i][w] = dp[i - 1][w]; // 裝不下，直接跳過
                }
            }
        }
        System.out.println("最優(yōu)組合價值：" + dp[weights.length][maxWeight]);
    }
}