背包问题

0-1背包问题解法

问题提出

背包问题。给定n个重量为 $w_{1},w_{2},\ldots,w_{n}$,价值为$v_{1},v_{2},\ldots,v_{n}$的物品和一个承重为W的背包，求将这些物品中的 某些装入背包中，在不超出重量W的情况下，价值最高的装法。

解法1——穷举法

算法描述

通过递归完成对所有解的遍历，记录遍历过程中的最优解

算法实现

#include <iostream>

using namespace std;

const int N = 4;  //物品个数
const int W = 10; //背包的容量

typedef struct commodity
{
    int weight; //重量
    int value;  //价值

    int flag;
} commodity;

commodity goods[N] = {{7, 42, 0}, {3, 12, 0}, {4, 40, 0}, {5, 25, 0}};
int r[N + 1] = {0};
int sum_w = 0, sum_v = 0;
int ans = 0;

int record(int sum_v)
{
    int count = 0;
    r[0] = sum_v;
    for (int i = 0; i < N; i++)
    {
        if (goods[i].flag)
            r[++count] = i + 1;
    }
    return count;
}
void knaps(int x)
{
    if (sum_w > W)
        return;
    if (sum_v > r[0])
        ans = record(sum_v);
    for (int i = x; i < N; i++)
    {
        sum_v += goods[i].value;
        sum_w += goods[i].weight;
        goods[i].flag = 1;
        knaps(i + 1);
        sum_v -= goods[i].value;
        sum_w -= goods[i].weight;
        goods[i].flag = 0;
        r[i] = 0;
    }
}

int main()
{
    knaps(0);
    cout << "有" << ans << "个物品被选中了" << endl;
    cout << "max value is:" << r[0] << endl;
    return 0;
}

时间复杂度分析

$$f(n)=\begin{cases}nf(n-1) +C & \text{n > 1} \\ 1 & \text{n=1} \end{cases}$$

可得：

$$f(n) = \Theta(n!)$$

运行结果

解法2——动态规划

计算模型

定义价值函数 $P(i,W)$：在 $i$件物品中选择总重量不超过 $W$的物品装入背包，记此时使得背包总价值最大的取值为：$m(i,W),\quad 1 \leq i \leq n, \quad 1 \leq W \leq C$

对于第 $i$个物品，存在两种情况：

• 不选，背包容量仍然为 $W$，问题变为 $P=(i-1,W)$
• 选，背包容量变小，问题变为 $P(i-1,W-w_{i})$

则，$m(i,W) = \max{\{ m(i-1,W),m(i-1,W-w_{i})+v_{i} \}}$

$$m(i, W)=\left\{\begin{array}{ll}0 & \text { if } i=0 \\ 0 & \text { if } W=0 \\ m(i-1, W) & \text { if } w_{i}>W \\ \max \left\{m(i-1, W), m\left(i-1, W-w_{i}\right)+v_{i}\right\} & \text { otherwise }\end{array}\right.$$

算法实现

#include <iostream>

using namespace std;

const int N = 4;  //物品个数
const int W = 10; //背包的容量

//初始物品信息
int m[N + 1][W + 1];

int max(int a, int b)
{
    return a > b ? a : b;
}

// n为物品数，W为背包容量，w[]、v[]分别为每个物品的重量与价值
void DP_Knapsac(int w[], int v[])
{
    int i, weight;
    for (i = 0; i <= W; i++)
        m[0][i] = 0;
    for (i = 1; i <= N; i++)
        m[i][0] = 0;
    for (i = 1; i <= N; i++)
    {
        for (weight = 1; weight <= W; weight++)
        {
            if (w[i] > weight)
                m[i][weight] = m[i - 1][weight];
            else
                m[i][weight] = max(m[i - 1][weight], m[i - 1][weight - w[i]] + v[i]);
        }
    }
}

void Selected_Item(int w[], int v[])
{

    int remainspace = W;
    //输出所选择的物品列表：
    for (int i = N; i >= 1; i--)
    {
        if (remainspace >= w[i])
        {
            if ((m[i][remainspace] - m[i - 1][remainspace - w[i]] == v[i]))
            {
                cout << "item of " << w[i] << "kg"
                     << " is selected" << endl;
                remainspace = remainspace - w[i]; //如果第i个物品被选择，那么背包剩余容量将减去第i个物品的重量 ;             }
            }
        }
    }
}

int main()
{
    int w[5] = {0, 7, 3, 4, 5};
    int v[5] = {0, 42, 12, 40, 25};
    DP_Knapsac(w, v);
    Selected_Item(w, v);
    return 0;
}

时间复杂度分析

求解函数DP_Knapsac的主要内容为两层for循环，则:

$$T(n) = \sum_{1}^{N}\sum_{1}^{W}C = O(N*W)$$

其中，N为物体总件数，W为背包总容量

运行结果