java解析背包問(wèn)題實(shí)例代碼(簡(jiǎn)單易懂)

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

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

問(wèn)題場(chǎng)景‌：

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

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

‌問(wèn)：怎么裝才能既不超過(guò)重量，又讓旅行最舒服？

1. 核心思想‌

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

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

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

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

2. 直接上代碼‌

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

        // 開(kāi)始填表
        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) {
                    // 能裝下時(shí)：比較"裝"和"不裝"哪個(gè)更劃算
                    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]; // 裝不下，直接跳過(guò)
                }
            }
        }
        System.out.println("最優(yōu)組合價(jià)值：" + dp[weights.length][maxWeight]);
    }
}