MATLAB 背包问题

背包问题

背包问题是数学建模中的一个经典问题，其目的是在给定的背包容量下，选择一组物品，使得物品的价值最大化。在实际生活中，背包问题可以用于物流运输、物资调度等领域。

常见的背包问题有 0-1 背包问题、完全背包问题、多重背包问题等。

0-1 背包问题

0-1 背包问题是最基本的背包问题，即每个物品只能选择 0 个或 1 个。

通常使用动态规划的方法求解 0-1 背包问题。

例

有 4 件物品，重量分别为 2、2、6、5，价值分别为 6、3、5、4，背包容量为 10，求背包中物品的最大价值。

解

  1. 将原问题分解为子问题：将问题分解为前 i 件物品放入容量为 j 的背包中所能获得的最大价值。
  2. 确定状态：i 件物品放入容量为 j 的背包中所能获得的最大价值。
  3. 确定一些初始状态（边界状态）的值：当 i = 0 时，j 件物品放入容量为 j 的背包中所能获得的最大价值为 0；当 j = 0 时，i 件物品放入容量为 j 的背包中所能获得的最大价值为 0。
  4. 确定状态转移方程：当 i 件物品放入容量为 j 的背包中所能获得的最大价值为 max{f(i-1,j),f(i-1,j-w(i))+v(i)}，其中 w(i) 为第 i 件物品的重量，v(i) 为第 i 件物品的价值。

可得出以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function [f, sol] = knapsack(w,v,c)
    % w: 物品重量
    % v: 物品价值
    % c: 背包容量
    n = length(w);
    f = zeros(n+1,c+1);  % f(i,j)表示前i-1件物品放入容量为j-1的背包中所能获得的最大价值
    flag = zeros(n+1,c+1);  % flag(i,j)表示前i-1件物品放入容量为j-1的背包中取得最大价值时放入物品的最大标号
    for i = 2:n+1
        for j = 2:c+1
            if w(i-1) < j
                if f(i-1,j) <= f(i-1,j-w(i-1))+v(i-1)
                    f(i,j) = f(i-1,j-w(i-1))+v(i-1);
                    flag(i,j) = i-1;
                else
                    f(i,j) = f(i-1,j);
                    flag(i,j) = flag(i-1,j);
                end
            else
                f(i,j) = f(i-1,j);
            end
        end
    end
    f = f(n+1,c+1);
    % 追踪解方案
    sol = zeros(1,n);
    for i = n+1:-1:2
        if flag(i,c+1) == i-1
            sol(i-1) = 1;
            c = c - w(i-1);
        end
    end
end

调用函数求解：

1
2
3
4
w = [2,2,6,5];
v = [6,3,5,4];
c = 10;
[f,sol] = knapsack(w,v,c)

结果：

1
2
3
4
5
f =
    14

sol =
     1     1     1     0

完全背包问题

完全背包问题是背包问题的一种，即每种物品可以选择任意个。

我们可以将其转化为 0-1 背包问题，即将每种物品拆分为若干个物品，每个物品的重量和价值都相同。

例

有 4 种物品，重量分别为 2、2、6、5，价值分别为 6、3、5、4，背包容量为 20，求背包中物品的最大价值。

解

将每种物品拆分为 c/w 个物品，并求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
w = [2,2,6,5];
v = [6,3,5,4];
c = 20;
n = size(w);

num = floor(c./w);
w = repelem(w,num);
v = repelem(v,num);
[f,sol] = knapsack(w,v,c);

solu = zeros(n);
base = 0;
for i = 1:n(2)
    for j = 1:num(i)
        solu(i) = solu(i) + sol(base+j);
    end
    base = base + num(i);
end

f,solu

结果：

1
2
3
4
5
f =
    60

solu =
    10     0     0     0

多重背包问题

多重背包问题是背包问题的一种，即每种物品可以选择有限个。

我们可以将其转化为 0-1 背包问题，即将每种物品拆分为若干个物品。

例

有 4 种物品，重量分别为 2、2、6、5，价值分别为 6、3、5、4，每种物品的数量分别为 3、1、2、1，背包容量为 20，求背包中物品的最大价值。

解

将每种物品拆分为 num(i) 个物品，并求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
w = [2,2,6,5];
v = [6,3,5,4];
num = [3,1,2,1];
c = 20;
n = size(w);

w = repelem(w,num);
v = repelem(v,num);
[f,sol] = knapsack(w,v,c);

solu = zeros(n);
base = 0;
for i = 1:n(2)
    for j = 1:num(i)
        solu(i) = solu(i) + sol(base+j);
    end
    base = base + num(i);
end

f,solu

结果：

1
2
3
4
5
f =
    31

solu =
     3     1     2     0