什么是Java數據結構

這篇文章主要講解了“什么是Java數據結構”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“什么是Java數據結構”吧！

 應用場景-背包問題

背包問題：有一個背包，容量為4磅，現有如下物品：

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. 要求達到的目標為裝入的背包的總價值最大，并且重量不超出

3. 要求裝入的物品不能重復

動態規劃算法介紹

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. 動態規劃(Dynamic Programming)算法的核心思想是：將大問題劃分為小問題進行解決，從而一步步獲取最優解的處理算法。

3. 動態規劃算法與分治算法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

4. 與分治算法不同的是，適用于動態規劃求解的問題，經分解得到子問題往往不是相互獨立的。(即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解)。

5. 動態規劃可以通過填表的方式來逐步推進，得到最優解。

背包問題分析

背包問題主要是指一個給定容量的背包、若干具有一定價值和重量的物品，如何選取物品放入背包是物品的價值最大。其中又分01背包和完全背包(完全背包指的是：每種物品都有無限件可用)。

這里的問題屬于01背包，即每個物品最多放一個，而無限背包可以轉化為01背包。

思路分析

算法的主要思想，利用動態規劃來解決。每次遍歷到的第i個物品，根據w[i]和v[i]來確定是否需要將該物品放入背包。即對于給定的n個物品，設v[i]、w[i]分別為第i個物品的價值和重量，C為背包的容量。再令v[i][j]表示在前  i 個物品中能夠裝入容量為 j 的背包的最大值。則有下面的結果：

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. v[i][0] = v[0][j] = 0;//表示填入表第一行和第一列是0

3. 當w[i]>j時：v[i][j]=v[i-1][j];//當準備加入的新增的商品的容量大于當前背包的容量時，就直接使用上一個單元格的裝入策略。

4. 當j>=w[i]時：v[i][j]=max{v[i-1][j],v[i]+v[i-1][j-w[i]]};//當準備加入的新增的商品的容量小于等于當前背包的容量，裝入的方式：v[i-1][j]：就是上一個單元格的裝入的最大值v[i]：當前商品的價值v[i-1][j-w[i]]：裝入i-1商品，到剩余空間[j-w[i]的最大值

填表的過程

代碼案例

package com.xie.algorithm;  import java.util.Arrays;  public class KnapsackProblem {     public static void main(String[] args) {         //物品的重量         int[] w = {1, 4, 3};         //物品的價值         int[] val = {1500, 3000, 2000};         //背包的容量         int m = 4;         //物品的個數         int n = val.length;          //為了記錄商品放入的情況，定義一個二維數組         int[][] path = new int[n + 1][m + 1];          //創建二維數組         //v[i][j]表示在前 i 個物品中能夠裝入容量為 j 的背包的最大值         int[][] v = new int[n + 1][m + 1];          //初始化第一行和第一列         //將第一列設置為0         for (int i = 0; i < v.length; i++) {             v[i][0] = 0;         }         //將第一行設置為0         for (int i = 0; i < v[0].length; i++) {             v[0][i] = 0;         }          //根據前面的公式來動態規劃處理         //不處理第一行         for (int i = 1; i < v.length; i++) {             //不處理第一列             for (int j = 1; j < v[0].length; j++) {                 //公式                 //因為我們的程序 i  是從1開始的，因此原來的公式中的w[i]修改成w[i-1]                 if (w[i - 1] > j) {                     v[i][j] = v[i - 1][j];                 } else {                     //因為我們的程序 i  是從1開始的                     //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);                     if (v[i - 1][j] > val[i - 1] + v[i - 1][j - w[i - 1]]) {                         v[i][j] = v[i - 1][j];                     } else {                         v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];                         //把當前的情況記錄到path                         path[i][j] = 1;                     }                 }             }         }          for (int i = 0; i < v.length; i++) {             System.out.println(Arrays.toString(v[i]));         }          int i = path.length - 1;         int j = path[0].length - 1;         while (i > 0 && j > 0) {             if (path[i][j] == 1) {                 System.out.printf("第%d個商品放入背包\n", i);                 j -= w[i - 1];             }             i--;         }     }      /**      * [0, 0, 0, 0, 0]      * [0, 1500, 1500, 1500, 1500]      * [0, 1500, 1500, 1500, 3000]      * [0, 1500, 1500, 2000, 3500]      * 第3個商品放入背包      * 第1個商品放入背包      */ }

感謝各位的閱讀，以上就是“什么是Java數據結構”的內容了，經過本文的學習后，相信大家對什么是Java數據結構這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！