动态规划3-贪心算法-0-1背包

参考

https://zh.wikipedia.org/wiki/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。^[1]比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

贪心算法，可以针对一些不是特别复杂的问题，也就是不需要推导重来，确定子结构最优解，这个最优解就是最终解的一部分，不会像动态规划中，可能随着子结构的增加而变化。

我们了解了贪心算法，也就是每一步都找最好的结果，那么与动态规划的区别的？唯一区别就是，贪心算法，每一步的最优解肯定是最后的最优解，不可能出现每一个子结构的最优解不是最终解的情况。如果出现了呢？那就是动态规划。也就是每一步的最优解，并不一定是最后的解，还需要判断，有肯能为了最终的解，而舍弃前面子结构中的最优解。

0-1背包

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

这是非常经典的一道题，0-1是计算机术语，就是每个物品只有一个，选择放（1）还是不放（0），求出最大财富。这个与动态规划1-国王和金矿一样。很多地方把这道题归于贪心算法，其实应该属于动态规划，因为每次装性价比最高的物品，并不一定是最后的最优解。

比如我们要求，输入的第一个是背包可装的重量。第二行，空格隔开是每个物品的重量。第三行，空格隔开是对应的物品价值。输出最高价值。进阶，输出最优解的选择。

推导公式f(n,v)=max(f(n-1,v),f(n-1,v-vn))；获取当前的最优解，就等于，把当前物品加进去，计算前面的最优解，加在一起；不把当前的物品加进去，计算前面的最优解，然后取这两个最大值。

void zobag(vector<int>& weights, vector<int>& wealths, int vbag, int index, map<int, bool>& selmap)
{
    if (index == 0)
    {
        if (weights[0] <= vbag)
        {
            selmap[0] = true;
        }
    }
    else
    {
        map<int, bool> selmap1 = selmap;
        zobag(weights, wealths, vbag, index - 1, selmap1);
        map<int, bool> selmap2 = selmap;
        if (vbag >= weights[index])
        {
            selmap2[index] = true;
        }
        zobag(weights, wealths, vbag - weights[index], index - 1, selmap2);
        int tmp1 = 0;
        int tmp2 = 0;
        for (auto& iter : selmap1)
        {
            if (iter.second)
            {
                tmp1 += wealths[iter.first];
            }
        }
        for (auto& iter : selmap2)
        {
            if (iter.second)
            {
                tmp2 += wealths[iter.first];
            }
        }
        if (tmp1 > tmp2)
        {
            selmap = selmap1;
        }
        else
        {
            selmap = selmap2;
        }
    }
}
int main()
{
    int vbag = 10;
    vector<int> weights = { 5, 3, 4, 3, 5 };
    vector<int> wealths = { 500, 200, 300, 350, 400 };
    map<int, bool> selmap;
    zobag(weights, wealths, vbag, weights.size() - 1, selmap);
    char inchar;
    cin >> inchar;
}

另一种更好的方法可以直接参考动态规划1-国王和金矿