恩恩，明白了，多谢哦

赞同倒数第二楼   看来得几个数组保存剩余量来弄这道题目了。。。。。初学者   求指教

这题目很简单，明天给你们贴代码
动态规划是递归的优化写法，

7楼说的有道理，不过你了解太少，很容易想当然了

[ 本帖最后由 BlueGuy 于 2015-6-6 00:10 编辑 ]

vector<int> items = {5, 4, 3, 2, 2, 2, 2};
vector<bool> isSelect(7);
vector<int> selected(7);

int knap(int cap)
{
    int remain = 0;
    int min = cap;
    
    for (int i = 0; i < items.size(); i++)
    {
        if (!isSelect[i])
        {
            remain = cap - items[i];
            
            if (remain >= 0)
            {
                isSelect[i] = true;
                int t = knap(remain);
                
                if (t < min)
                {
                    selected.clear();
                    
                    for (int j = 0; j < items.size(); j++)
                    {
                        if (isSelect[j])
                        {
                            selected.push_back(items[j]);
                        }
                    }
                    
                    min = t;
                }
                
                
            }
            
            isSelect[i] = false;
        }
    }
    
    return min;
}

int main(void)
{
    int count = 0;
    
    while (true)
    {
        count++;
        knap(10);
        
        for (int i = 0; i < selected.size(); i++)
        {
            for (int j = 0; j < items.size(); j++)
            {
                if (items[j] == selected[i])
                {
                    items.erase(items.begin()+j);
                }
            }
        }
        
        if (items.size() == 0)
        {
            break;
        }
        
        isSelect.clear();
        isSelect.resize(items.size());
        
        selected.clear();
        selected.resize(items.size());
    }
    
    return 0;
}

有点bug，改天再改改

这题可以当组合来解，肯定不容易出bug了

[ 本帖最后由 BlueGuy 于 2015-6-6 15:35 编辑 ]

你这叫“有点bug”？不能谁随便扔段代码上来只要能编译通过就说把问题解决了吧？

话说你的天下第一什么时侯上线呀？我还打算跟你要首测的帐号呢。

没什么进展，各种欠缺啦，

业余爱好吧，不要报太多期望

我有资格调侃他，但你们没有。他算法方面不如我，但也足够在你们面前炫耀。他的编程经验足以指导这里绝大多数人。

他的代码想穷举求单背包，再贪心求多背包。可惜，1、逻辑存在问题不能完成他的想法；2、即使逻辑正确算法本身也存在陷入局部最优的缺陷；3、时间效率低几乎无用。

至少他还能有个思路写出点代码，更多人是看热闹吧。

动态规划 我不太熟练，但是一天肯定是能解出来的了，
所以我没用动态规划，用了递归，为了节省代码，出了一点bug,
但是也很容易改过来，

背包容量C 为目标量，任意和为C的记一个背包。 计算完毕后计算C-1为目标重量的记一个背包， 下面计算C－2为目标重量的 以此类推 然后记总背包数量