背包问题

0-1背包问题；

问题：假设你有一个背包其能容纳物品的最大重量为8，现在有如下几件物品：

物品编号	1	2	3	4
重量	2	3	4	5
物品价值	3	4	5	6

现在需要让你选择选择物品装入背包中，在不超过背包的最大重量的情况下，使获得的物品总价值最大。

首先列出解决这个问题的公式：

利用公式画出如下一个二维矩阵，表示当前背包容量和当前物品编号之间的关系。

背包容量 ----------- 物重物品量品编价号值	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1 2 3	0	3	3	3	3	3	3	3
2 3 4	0	3	4	4	7	7	7	7
3 4 5	0	3	4	5	7	8	9	9
4 5 6	0	3	4	5	7	8	9	10

第一行和第一列全部为0，因为背包为0的时候无法装下任何东西，物品编号为0表示什么都没有。

计算（1 ,1）位置的值，背包容纳量为1，发现背包重量小于编号为1物品的重量，无法放入所以价值为0。

计算（1 ,2）位置的值，背包容纳量为2，发现背包重量刚好等于编号为1物品的重量，可以放入背包价值为3

.................................

计算（2 ,2）位置的值，背包容纳量为2，出现选择第二个品能否放入背包？不能，那就还放之前的（1 ,2）的价值的物品，对应公式中的（3）。

计算（2 ,3）位置的值，背包容纳量为3，出现选择第二个物品能否放入背包？可以，出现两种选择。第一种不放这个物品到当前背包，则还放入之前（1 ,3）的物品价值，对应公式中的（2）；第二种选择放入背包，则物品的价值为当前物品价值+（1,4-4）位置处的物品价值。其中4-4是去除当前物品重量后，还有多少容量，对应公式中的（3）。

...................................

后面的计算类似，经过全部计算后最右下角的值就是问题的答案。

如果想知道放入了几件物品该怎么办呢？利用回溯解决该问题。

从最右下角（4,8）位置开始判断4号物品是否放入背包，首先看同一列的上一行的值判断该行的物品是否放入背包。通过上述的放入规则，得知当两个值不同时，则表示该物品放入了背包。所以编号为4的物品放入了背包。当4号物品放入背包号，背包的当前容量就位8-5=3，我们接着判断3号物品是否放入背包，查看（3,3）位置和其上一行相同列的值是否相同，相同则没有放入。接着判断2号物品是否放入了背包，查看（2,3）位置和其上一行相同列的值是否相同，发现不同则2号物品放入了背包，背包的容量为3-2=1，接着判断1号物品是否放入了背包，查看（1,1）位置和上一行相同列的值是否相同，相同没有放入。经过这样的搜索过程，可以发现（2，4）物品最终放入了背包。

代码实现：

#include<iostream>
#include<algorithm>

using namespace std;

//第一个数字表示物品个数 +1需要多一行一列
const int ITEM = 4+1;
//第一个数字表示背包容量
const int CAPACITY = 8+1;

// 创建一个二维数组存储每次计算数值
int B[ITEM][CAPACITY] = {0};
//物品重量
int w[6] = { 0,2,3,4,5 };
//物品价值
int v[6] = { 0,3,4,5,6 };

void knapsack() 
{
    //k表示当前k个物品
    //c表示当前背包的容量
    int k, c;
    //计算值填入B中
    for (k = 1; k < ITEM; k++)
    {
        for (c = 1; c < CAPACITY; c++)
        {
            //第一种情况当前物品的重量大于剩余背包重量，放不下
            //当前物品重量如果大于背包的容量 
            //当前背包背包价值为B[k-1][c]
            if (w[k] > c) 
            {
                B[k][c] = B[k - 1][c];
            }
            //能够放下考虑两种情况 放还是不放
            //然后取其中的最大值作为当前的价值
            else
            {
                //放当前物品 
                //则价值为当前物品价值+
                //除去当前物品重量后的物品的最大价值
                int value1 = B[k - 1][c - w[k]] + v[k];
                //不放当前物品
                //则为之前所放物品的价值
                int value2 = B[k - 1][c];
                //求两种可能的最大值
                B[k][c] = max(value1, value2);
                /*if (value1 > value2)
                {
                    B[k][c] = value1;
                }
                else
                {
                    B[k][c] = value2;
                }*/
            }
        }
    }
}

int main()
{
    knapsack();
    cout << B[4][6] << endl;
    system("pause");
    return 0;
}