01背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
01背包问题为最简单的背包问题,即限定每种物品只能选择0个或1个。
下面介绍一个很简单的01背包问题以供参考。

问题描述

有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,每件物品数量只有一个,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?

问题分析

将该问题转换成子问题,考虑五件物品在给定承重 C 的背包下最大价值为原问题,即为考虑在abcde五件物品中进行选择,最大承重C = 10时的最大价值,假设为f[5][10],则原问题的解可以分解为两种情况:

  1. 不考虑放入a只考虑放入bcde承重为C时的最大价值f[4][C]

  2. 第二种情况是考虑放入a时的最大价值,即value[a]+f[4][10-weight[a]]

原问题的解f[5][10]取上述两种情况中的最大值,即f[5][10] = max{f[4][10], (f[4][10-weight[a]+value[a]))}。由此可以看出里面涉及到需要计算f[4][10]和f[4][10-weight[a]]即f[4][4]等子问题。 以此类推,自顶向下的分析可以看出原问题需要子问题的解,我们需要先计算出子问题的解,自底向上求解。注意此问题中的abcde可以包含相同的物件,它们之间的顺序也可以是任意的,不影响最终的结果。

按上述描述的递推公式计算时,我们需要初始值,f[i][0]=0(1<=i<=5), f[1][j]=(j < weight[e])?0:value[e],(1<=j<=10)。

代码

#include <iostream>
using namespace std;

int knapsack(int *W, int *V, int n, int C)
{
    int value = 0;

    int **f = new int*[n];
    for (int i = 0; i < n; i++)
    {
        f[i] = new int[C + 1];
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= C; j++)
            f[i][j] = 0;

    for (int i = 1; i <= C; i++)
    {
        f[0][i] = (i < W[0]) ? 0 : V[0];
    }

    for (int i = 1; i < n; i++)
    {
        for (int y = 1; y <= C; y++)
        {
            if (y >= W[i])
            {
                f[i][y] = (f[i - 1][y] >(f[i - 1][y - W[i]] + V[i])) ? f[i - 1][y] : (f[i - 1][y - W[i]] + V[i]);
            }
            else {
                f[i][y] = f[i - 1][y];
            }
        }
    }

    value = f[n - 1][C];

    for (int i = 0; i < n; i++)
    {
        delete f[i];
        f[i] = 0;
    }
    delete[] f;
    f = 0;
    return value;
}

int main()
{
    int C, n;   //C为最大承重,n为可供选择的物品总数
    cin >> C >> n;
    int *W = new int[n];    //每个物品的重量
    int *V = new int[n];    //每个物品的价值
    int w = 0, v = 0, i = 0;
    while (i < n)
    {
        cin >> w >> v;
        W[i] = w;
        V[i] = v;
        i++;
    }
    int value = knapsack(W, V, n, C);
    cout << value;
    delete W;
    delete V;
    return 0;
}

输入:

5 10 //5种物品,背包承重为10
2 6 //第一种物品,重量为2,价值为1,数目1个
2 3
6 5
5 4
4 6

输出:

15