Study dynamic programming - back pack problem - Feb. 14, 2018

studyBackPack.cpp

/*
01背包问题
背包九讲：http://www.cnblogs.com/jbelial/articles/2116074.html

其状态转移方程便是：f[i][v] = max{f[i-1][v], f[i-1][v-c[i]] + w[i]}。 

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。

**详细解释**

“将前 i 件物品放入容量为 v 的背包中” 这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就
可以转化为一个只牵扯前 i-1 件物品的问题。如果不放第 i 件物品，那么问题就转化为“前 i-1 件物品放入
容量为 v 的背包中”；如果放第 i 件物品，那么问题就转化为“前 i - 1 件物品放入剩下的容量为 v - c[i]的背包中”，
此时能获得的最大价值就是 f [i - 1][v - c[i]]再加上通过放入第 i 件物品获得的价值 w[i]。 
*/

int main()
{
    //int m = 120;
    //int n = 5;
    //vector<int> w = { 0, 40, 50, 70, 40, 20 };
    //vector<int> v = { 0, 10, 25, 40, 20, 10 };

    int m, n;    //m重量，n数量
    while (cin >> m >> n)
    {
        vector<int> w(n + 1, 0);
        vector<int> v(n + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            int tmp;
            cin >> tmp;
            w[i] = tmp;
        }
        for (int i = 1; i <= n; i++)
        {
            int tmp;
            cin >> tmp;
            v[i] = tmp;
        }
        vector< vector<int> > vec(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (w[i] > j)
                    vec[i][j] = vec[i - 1][j];
                else
                {
                    int tmp1 = v[i] + vec[i - 1][j - w[i]];
                    int tmp2 = vec[i - 1][j];
                    vec[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
                }
            }
        }
        
        double val = vec[n][m] * 0.1;
        cout << val << endl;
    }

    system("pause");
}