0-1背包問題 動态規劃java_Java-01背包問題-動态規劃-遞歸和非遞歸實作

國際慣例，先上代碼，粗略分析：

package com.bag;

public class Main {

static int totalweight= 150;

static int N= 5;

static int values[] = {60, 20, 10, 60, 100};

static int weights[] = {20, 30, 50, 60, 80};

public static void main(String[] args) {

System.out.println(bagProblem(N-1,totalweight));

bag01();

}

//遞歸實作

// i {處理到第i件物品} , j{剩餘的空間為j}

public static int bagProblem(int i, int j) {

int r = 0;

if(i==-1){

return 0;

}

//如果剩餘空間大于所放的物品

if (j>=weights[i]){

int r1 = bagProblem(i-1,j-weights[i]) + values[i]; //放第i件

int r2 = bagProblem(i-1,j);//不放第i件

r = Math.max(r1,r2);

}

return r;

}

//非遞歸

public static void bag01(){

int f[] = new int[totalweight+1];

for (int f1:f){

f1 = 0;

}

for (int i=0;i

int w = weights[i];

int v = values[i];

for (int j= totalweight;j>=w;j--){

f[j] = Math.max(f[j],f[j-w]+v);

}

}

System.out.println(f[totalweight]);

}

}

遞歸實作思路：

重點是尋找狀态轉移方程

intr1 = bagProblem(i-1,j-weights[i]) + values[i]; //放第i件intr2 = bagProblem(i-1,j);//不放第i件r = Math.max(r1,r2);

非遞歸實作思想:

建立0-totalweights共total+1大小的數組，用來存放價值。

第一步，先任意拿一個物品，進行周遊存放。

第二步，拿第二個物品，進行存放并且和之前的資料進行對比。存放大值。

以此類推，直至循環完成，取最後一個值，即為最大值。

舉例，背包大小為10，物品有3個，重量和價值，分别是：3,4 4,5 5,6

第一次，放3,4，則數組從a[0]到a[10]分别是：

0 0 0 4 4 4 4 4 4 4 4

第二次，放4,5，分别是

0 0 0 4 5 5 5 9 9 9  9

第三次，放5,6，分别是

0 0 0 4 5 6 6 9 10 11 11

循環完畢，a[10] = 11。