📖題目描述

求背包裝入最大價值

物品（件）重量（千克）價值（元）

8倍鏡	2	7
急救包	4	8
子彈	6	9
AWM狙擊步槍	8	2

📖動態規劃求解

/*** 0-1背包問題【動態規劃】** @param W 背包可以裝入的總重量* @param N 背包可以放入的物品數量* @param wt 各個物品的重量* @param value 各個物品對應的價值* @return 背包可以裝入的最大價值*/static int knapsack(int W, int N, int[] wt, int[] value) {int[][] dp = new int[N + 1][W + 1];for (int i = 1; i <= N; i++) {for (int w = 1; w <= W; w++) {if (w - wt[i - 1] < 0) {// 不裝入背包dp[i][w] = dp[i - 1][w];} else {// 裝入或者不裝入背包（擇優）dp[i][w] = Math.max(dp[i - 1][w - wt[i - 1]] + value[i - 1], dp[i - 1][w]);}}}return dp[N][W];}

📖測試結果

假如背包容量為16，裝入3件物品，得到的最大價值為24。

public static void main(String[] args) {int[] wt = {2,4,6,8};int[] val = {7,8,9,2};int knapsack = knapsack(16, 3, wt, val);System.out.println(knapsack);}

總結

以上是生活随笔為你收集整理的动态规划求解0-1背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。