数据结构：背包问题

梦里梦外; 2022-05-31 12:51 121阅读 0赞

# 背包问题 #

对于0-1背包，也即每一个背包只能选择放入和不放入，不可以部分放入，这就是0-1的含义，这个时候直接DP即可，贪心算法可能无法得到最优解，

对于其他背包问题，允许部分放入，可以使用贪心算法，正对背包的密度做一个排序即可就可以了，这个时候贪心算法得到的就是最优解，

# 代码详解 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    //0-1背包问题:这个指的是有k个商品要放入一个背包内,每一个商品只能选择放入或者不放入,不可以部分放入,这个就是0-1背包问题
    //0-1背包问题必须使用动态规划去做,贪心算法可能得不到最优解
    
    //还存在分数背包问题,这个问题讲的是物品可以部分放入背包内,这个使用贪心算法就可以啦,贪心算法可以的最优解
    //具体算法思路就是,把单位重量价值最高的物品往背包里面放,这个就是"分数"的意思
    
    //本体描述的是0-1背包
    void BagByDP()
    {
        int wei[3] = { 3,4,5 };
        int val[3] = { 4,5,6 };
    
        //描述的是有3个物品背包容量最大为10的问题
        int m[4][11] = { 0 };
        //标记数组,这个和最长公共序列类似
        int vis[4][11] = { 0 };
    
        //m[i][j]表示的意思是前i个商品放入到容量为j的背包中的最大价值,我们的目标就是m[3][10]
        //那么有如下的递推公式:      wei[i] > j 的时候,物品i无法放入,那么m[i][j]=m[i-1][j];
        //                          wei[i] <= j 的时候,物品i可以选择放入或者不放入,那么m[i][j]=max( m[i-1][j-wei[i-1]]+val[i-1],m[i-1][j]);
        for (int j = 1; j <= 10; j++)
        {
            for (int i = 1; i <= 3; i++)
            {
                if (wei[i - 1] > j)
                {
                    m[i][j] = m[i - 1][j];
                    //设计为-1是为了标示物品的选择
                    vis[i][j] = -1;
                }
                else
                {
                    int tmp = m[i - 1][j - wei[i - 1]] + val[i - 1];
                    if (tmp > m[i - 1][j])
                    {
                        m[i][j] = tmp;
                        vis[i][j] = i;
                    }
                    else {
                        m[i][j] = m[i - 1][j];
                        vis[i][j] = -1;
                    }
                }
            }
        }
    
    
        cout << "Max Weight is :" << m[3][10] << endl;
        vector<int> res;
        int i = 3, j = 10;
        while (vis[i][j] != 0)
        {
            if (vis[i][j] != -1)
            {
                int k = vis[i][j];
                res.push_back(k);
                i--;
                j = j - wei[k - 1];
            }
            else
                i--;
        }
    
        cout << "The Following Bags is chosen: " << endl;
        for (int i = 0; i<res.size(); i++)
            cout << res[i] << " ";
        cout << endl;
    }
    
    
    int main()
    {
        BagByDP();
        system("pause");
    }