給定
種物品和一個背包。物品
的重量是
，其價值為
，背包的容量為
。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大? （
,
和
都是整數）
定義子問題
将物品用 1,2,... ,n編号, 子問題可以定義為
= {在1, 2, ... , k号物品中找最優解}
問題是: 我們能否将問題(
)的最優解 用子問題 (
)的最優解表示?
定義新的子問題
1.增加一個參數 w :
中的物品的重量
2.定義 B[w][k] =放入背包中的編号不超過k、重量不超過w的物品的總價值.
附java代碼
package package0_1;
/**
* 0-1背包問題
* @author Dudu
* @date 2018-11-11
*/
public class Knapsack0_1Algorithm {
public static void marknumber(int n,int W,int[][] B ,int[] b,int v)
{
//給選擇到的物品打标号1 表示選擇 ，0表示不選
int[] x = new int[n];
while (v > 0) {
flag:for (int i = 1;i <= n;i++) {
for (int w = 1;w <= W;w++) {
if (B[w][i] == v) {
//按列選擇第一個達到最優值的位置得到第一個編号，減去目前編号的價值，得到上一個物品的價值，再去搜尋上一個物品的編号
x[i-1] = 1;
v = v - b[i-1];
break flag;
}
}
}
}
System.out.print("選擇裝入背包的物品編号為："); //從1開始編号
for (int j = 0;j < n;j++) {
if (x[j] == 1) {
System.out.print(j+1+" ");
}
}
System.out.println();
}
public static int knapsack0_1(int n,int[] b,int[] wlist,int W) {
/**
* n: 物體總數
* b: 價值數組 存放每個物品的價值
* wlist: 重量數組 存放每個物品的重量
* W： 背包所能夠承載的總重量
*/
int[][] B = new int[W+1][n+1];
for (int w = 0;w <=W;w++) {
B[w][0] = 0;
}
for (int i = 1;i <= n;i++) {
B[0][i] = 0;
for (int w = 1;w <= W;w++) {
try {
if (wlist[i-1] <= w) {
B[w][i] = Math.max(b[i-1] + B[w-wlist[i-1]][i-1], B[w][i-1]);
// if (b[i-1] + B[w-wlist[i-1]][i-1] > B[w][i-1])
// {
// B[w][i] = b[i-1] + B[w - wlist[i-1]][i-1];
// }
// else {
// B[w][i] = B[w][i-1];
// }
}
else
{
B[w][i] = B[w][i-1];
}
}catch(IndexOutOfBoundsException e){
System.out.println("IndexOutOfBoundsException");
continue;
}
}
}
System.out.println("輸出B矩陣如下：行代表W，列代表物品編号n");
for (int w = 0;w <= W;w++) {
for (int i = 0;i <= n;i++) {
System.out.print(B[w][i]+"\t");
}
System.out.println();
}
marknumber(n,W,B,b,B[W][n]);
return B[W][n];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] w = {2,3,4,5,9};
int[] b = {3,4,5,8,10};
int n = w.length;
int W = 20;
int value = knapsack0_1(n,b,w,W);
System.out.println("價值為："+value);
}
}
輸出結果
輸出B矩陣如下：行代表W，列代表物品編号n
0 0 0 0 0 0
0 0 0 0 0 0
0 3 3 3 3 3
0 3 4 4 4 4
0 3 4 5 5 5
0 3 7 7 8 8
0 3 7 8 8 8
0 3 7 9 11 11
0 3 7 9 12 12
0 3 7 12 13 13
0 3 7 12 15 15
0 3 7 12 16 16
0 3 7 12 17 17
0 3 7 12 17 17
0 3 7 12 20 20
0 3 7 12 20 20
0 3 7 12 20 21
0 3 7 12 20 22
0 3 7 12 20 23
0 3 7 12 20 25
0 3 7 12 20 26
選擇裝入背包的物品編号為：1 3 4 5
價值為：26