目? ?錄

嗶哩嗶哩網站——動態規劃基礎 背包問題(1) 01背包

嗶哩嗶哩網站——【動態規劃】背包問題

---

百度百科——背包問題

嗶哩嗶哩網站——動態規劃基礎 背包問題(1) 01背包

視頻網址——嗶哩嗶哩網站——動態規劃基礎 背包問題(1) 01背包

?

? ?滾動數組

背包問題——優化算法——階梯跳躍點

// #include "everything.h" #include <bits/stdc++.h> // 錯誤代碼using namespace std;int N, V, dp[1001][100001], c[100001], w[100001]; // c重量、w價值int main() {int i, j;cin >> N >> V;for (i = 1; i <= N; i++)cin >> c[i] >> w[i]; // 讀入每個物品的重量與收益for (i = 1; i <= N; i++){for (j = V; j >= 0; j--){if (j < c[i])break;dp[j] = max(dp[j], dp[j - c[i]] + w[i]);}}cout << dp[V] << endl;system("pause");return 0; }

嗶哩嗶哩網站——【動態規劃】背包問題

視頻網址——嗶哩嗶哩網站——【動態規劃】背包問題

回溯：沒有與10相同的，所以物品4一定被裝入背包了。背包空間為8，物體4體積為5，背包中剩余的空間“3”用來裝其它物品。考慮背包容量為3的時候，最佳物品組合。--> 考慮3號物品到底有沒有被裝入背包 --> 若3號物品未被裝入背包，考慮前兩個物品裝入背包的情況即可。

? ?

Java代碼實現：https://www.cnblogs.com/jiyongjia/p/13475026.html

代碼——原文鏈接

package Z;import java.util.ArrayList; import java.util.LinkedHashMap; import java.util.List; import java.util.Map;public class Beibao {public static void main(String[] args) {Map<Integer, Integer> map = new LinkedHashMap<>();map.put(2, 3);map.put(3, 4);map.put(4, 5);map.put(5, 6);System.out.print("背包可容納最大價值：" + getMaxValue(map, 8));}private static Integer getMaxValue(Map<Integer, Integer> gems, int capacity) {int[][] maxValue = new int[gems.size() + 1][capacity + 1];List<Integer> gemList = new ArrayList<>();int choose, notChoose;for (int i = 0; i < gems.size() + 1; i++) {maxValue[i][0] = 0;}for (int i = 0; i < capacity + 1; i++) {maxValue[0][i] = 0;}gemList.add(0);for (Integer gemKey : gems.keySet()) {gemList.add(gemKey);}for (int i = 1; i < gems.size() + 1; i++) {for (int j = 1; j < capacity + 1; j++) {if (gemList.get(i) > j) {maxValue[i][j] = maxValue[i - 1][j];} else {choose = gems.get(gemList.get(i)) + maxValue[i - 1][j - gemList.get(i)];notChoose = maxValue[i - 1][j];maxValue[i][j] = Math.max(choose, notChoose);}}}for (int i = 0; i < gems.size() + 1; i++) {for (int j = 0; j < capacity + 1; j++) {System.out.print(maxValue[i][j] + " ");}System.out.println();}getDetails(maxValue, gems, gemList, gems.size() + 1, capacity + 1);return maxValue[gems.size()][capacity];}private static void getDetails(int[][] maxValue, Map<Integer, Integer> gems, List<Integer> gemList, int rows, int cols) {List<Integer> details = new ArrayList<>();while (rows > 1 && cols > 1) {if (maxValue[rows - 1][cols - 1] != maxValue[rows - 2][cols - 1]) {details.add(rows - 1);rows--;cols = cols - 1 - gemList.get(rows - 1);} else {rows--;}}System.out.println("裝入背包的有：");for (int i = 0; i < details.size(); i++) {System.out.println("體積為" + gemList.get(details.get(i)) + ",價值為" + gems.get(gemList.get(details.get(i))) + "的石頭");}}}

多謝觀看、

總結

以上是生活随笔為你收集整理的动态规划（dynamic programming）基础【背包问题】的全部內容，希望文章能夠幫你解決所遇到的問題。

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