1.問題給定的已知
N種物品和一個背包，物品的種類為wi，價值為vi，背包容量為C

2.所求目標
如何選擇裝入背包的物品，使得物品的總價值最大

3.數學模型

4.最優質子結構分析

現將問題分為n個子問題
（1）背包容量為c，從1號物品找出該問題的解
（2）背包容量為c，從1、2號物品找出該問題的解
（3）背包容量為c，從1、2、3號物品找出該問題的解
（4）背包容量為c，從1、2、3、4號物品找出該問題的解
……
（5）背包容量為c，從1、2、3、4、…N號物品找出該問題的解

5.建立最優值得遞歸關系式
遞推式：M[i, j] = max{m[i+1,j]，m(i-1,j-w[i])+v[i]}
邊界條件：j>=w[i]

6.程序代碼

public class Package01 {private int[][] nums;private int[] weight;private int[] value;int maxWeight;public Package01(int[] weight, int[] value, int maxWeight) {this.weight = weight;this.value = value;this.maxWeight = maxWeight;nums = new int[weight.length + 1][maxWeight + 1];}/*** i代表物品* j代表背包容量*/public void maxValue() {for (int i = 1; i <= weight.length; i++) {for (int j = 1; j <= maxWeight; j++) {if (j < weight[i - 1]) {nums[i][j] = nums[i - 1][j];} else {nums[i][j] = Math.max(nums[i - 1][j], nums[i - 1][j - weight[i - 1]] + value[i - 1]);}}}}public void print() {int i = nums.length;int j =nums[0].length;for (int k = 0; k < i; k++) {for (int s = 0; s < j; s++) {System.out.print(nums[k][s]+" ");}System.out.println();}}//測試public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {1500, 2000, 3000};Package01 p = new Package01(weight, value, 4);p.maxValue();p.print();}}

7.測試數據

第一組：

第二組:

8.結果分析

測試結果正確

以上方法的時間和空間復雜度均為O(N*V）

總結

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

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