【面试题】简单背包问题

96 阅读 0 评论 64 点赞

我是靠谱客的博主生动皮带，这篇文章主要介绍【面试题】简单背包问题，现在分享给大家，希望可以做个参考。

问题描述

假设有一个能装入总体积为T的背包和N件体积分别任w1、w2、w3、……wn的物品，能否从n件物品中挑选若干件恰好装满背包，即w1+w2+……Wn = T，要求满足上述条件的解。

例如，当T = 10，各件物品的体积为{1、8、4、3、5、2}时，可以
找到下列4组解：
(1,4,3,2)、(1，4，5)、(8，2)、(3，5，2)

分析问题

可以借助栈来存储，各种物品来计算物品的值。栈中存储的是物品的下标，这样方便当前物品不满足时，得到下一种物品。
i为物品的下标，控制栈中物品是否遍历。
res中保存的各种解，

下面的方法类似于暴力枚举法，

复制代码

// 把背包的索引放在栈中

int main()
{
    int wight = 10; //背包总重量
    int goods[] = {1,8,4,3,5,2};
    stack<int> goodstack; //存放物品下标
    vector<stack<int> > res;
    int Count = 0; //计已查物品的总重
    int i = 0; //数组下标

goodstack.push(i);
    Count += goods[i];
    i++;
    if (Count == wight)
    {
        res.push_back(goodstack);
        Count -= goods[i-1];
        goodstack.pop();
        goodstack.push(i++);
    }
    while (true)
    {
        while (!goodstack.empty() && i < 6)
        {
            goodstack.push(i);
            Count += goods[i];
            if (Count == wight)
            {
                res.push_back(goodstack);
                goodstack.pop();
                Count -= goods[i];
                i++;
            }
            else if (Count > wight) //大的话弹出
            {
                Count -= goods[i];              
                goodstack.pop();
                i++;
            }
            else
            {
                i++;
            }

}

if (i == 6 && !goodstack.empty())
        {
            i = goodstack.top() + 1;
            goodstack.pop();
            Count -= goods[i - 1];
        }
        //以i开始的完了
        if (goodstack.empty() && i < 6)
        {
            goodstack.push(i);
            Count += goods[i];
            i++;
            if (Count == wight)
            {
                res.push_back(goodstack);
                Count -= goods[i - 1];
                goodstack.pop();
                goodstack.push(i++);
            }
        }
        else if (goodstack.empty() && i == 6)
            break;

}
    system("pause");
    return 0;
}

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 把背包的索引放在栈中

int main()
{
    int wight = 10; //背包总重量
    int goods[] = {1,8,4,3,5,2};
    stack<int> goodstack; //存放物品下标
    vector<stack<int> > res;
    int Count = 0; //计已查物品的总重
    int i = 0; //数组下标

    goodstack.push(i);
    Count += goods[i];
    i++;
    if (Count == wight)
    {
        res.push_back(goodstack);
        Count -= goods[i-1];
        goodstack.pop();
        goodstack.push(i++);
    }
    while (true)
    {
        while (!goodstack.empty() && i < 6)
        {
            goodstack.push(i);
            Count += goods[i];
            if (Count == wight)
            {
                res.push_back(goodstack);
                goodstack.pop();
                Count -= goods[i];
                i++;
            }
            else if (Count > wight) //大的话弹出
            {
                Count -= goods[i];              
                goodstack.pop();
                i++;
            }
            else
            {
                i++;
            }

        }   

        if (i == 6 && !goodstack.empty())
        {
            i = goodstack.top() + 1;
            goodstack.pop();
            Count -= goods[i - 1];
        }
        //以i开始的完了
        if (goodstack.empty() && i < 6)
        {
            goodstack.push(i);
            Count += goods[i];
            i++;
            if (Count == wight)
            {
                res.push_back(goodstack);
                Count -= goods[i - 1];
                goodstack.pop();
                goodstack.push(i++);
            }
        }
        else if (goodstack.empty() && i == 6)
            break;

    }
    system("pause");
    return 0;
}