背包问题学习笔记 / Dynamic Programming（updating）

01背包问题

朴素版：（二维数组）

状态表示： dp[i][j]：从前i个物品中选择(每个物品只能选0或1个)且总体积不超过j的集合的最大价值，则dp[n][m]就是最终答案（n：物品数量，m：最大体积）

状态计算： dp[i][j] = max ( dp[i-1][j] , dp[i-1][j-v_i]+w_i ) // 由含i和不含i两个子集合计算而来（v_i：物品体积，w_i：物品价值）

核心代码：

int n, m; // n：物品数量, m：最大体积

int v[N], w[N], dp[N][M];

void keyCode()

{

    for(int i = 1; i <= n; i++)

        for(int j = 0; j <= m; j++)

        {

            dp[i][j] = dp[i-1][j];

            if(v[i] >= j) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);

        }

}

空间优化版：（滚动数组，二维数组优化至一维）

　　状态表示：dp[j]：在外循环的第i层时，表示从前i个物品中选择(每个物品只能选0或1个)且总体积不超过j的集合的最大价值，n层循环后，dp[m]就是最终答案

　　状态计算：dp[j] = max ( dp[j] , dp[j-v_i]+w_i ) // 由含i和不含i两个子集合计算而来

　　核心代码：

int n, m; // n：物品数量, m：最大体积

int v[N], w[N], dp[N];

void keyCode()

{

    for(int i = 1; i <= n; i++)

        // 反向遍历, 否则dp[j-v[i]]可能为dp[i][j-v[i]](用更新后的值来更新导致出错）

        for(int j = m; j >= v[i]; j--)

            dp[j] = max(dp[j], dp[j-v[i]] + w[i]); 

}

完全背包问题

朴素版：（二维数组）

　　状态表示：dp[i][j]：从前i种物品中选择(每种物品可以任选个数)且总体积不超过j的集合的最大价值，则dp[n][m]就是最终答案

　　状态计算：dp[i][j] = max ( dp[i-1][j] , dp[i][j-v_i]+w_i )

　　证明：dp[i][j] = max ( dp[i-1][j] , dp[i-1][j-v_i]+w_i, dp[i-1][j-2v_i]+2w_i, dp[i-1][j-3v_i]+3w_i, ...... )

　　　　　 dp[i][j-v_i] = max ( dp[i-1][j-v_i] , dp[i-1][j-2v_i]+w_i, dp[i-1][j-3v_i]+2w_i, ...... )

　　　　　 Thus，dp[i][j-v_i]+w_i = max ( dp[i-1][j-v_i]+w_i , dp[i-1][j-2v_i]+2w_i, dp[i-1][j-3v_i]+3w_i, ...... )

　　　　　 Thus，dp[i][j] = max ( dp[i-1][j] , dp[i][j-v_i]+w_i )

　　核心代码：

int n, m; // n：物品数量, m：最大体积

int v[N], w[N], dp[N][M];

void keyCode()

{

    for(int i = 1; i <= n; i++)

        for(int j = 0; j <= m; j++)

        {

            dp[i][j] = dp[i-1][j];

            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i]);

        }

}

空间优化版：（滚动数组，二维数组优化至一维）

　　状态表示：dp[j]：在外循环的第i层时，表示从前i种物品中选择(每种物品可以任选个数)且总体积不超过j的集合的最大价值，n层循环后，dp[m]就是最终答案

　　状态计算：dp[j] = max ( dp[j] , dp[j-v_i]+w_i ) // 由含i和不含i两个子集合计算而来

　　核心代码：

int n, m; // n：物品数量, m：最大体积

int v[N], w[N], dp[N];

void keyCode()

{

    for(int i = 1; i <= n; i++)

        // 正向遍历, 使得dp[j-v[i]]为dp[i][j-v[i]]

        for(int j = v[i]; j <= m; j++)

            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);

}

多重背包问题

朴素版：（二维数组+三重循环）

　　状态表示：dp[i][j]：从前i种物品中选择(每种物品最多选择s_i个)且总体积不超过j的集合的最大价值，则dp[n][m]就是最终答案

　　状态计算：dp[i][j] = max ( dp[i-1][j]，dp[i-1][j-v]+w，dp[i-1][j-2v]+2w，...，dp[i-1][j-sv]+sw )

　　核心代码：

int n, m; // n：物品数量, m：最大体积

int v[N], w[N], s[S];

int dp[N][M];

void keyCode()

{

    for(int i = 1; i <= n; i++)

        for(int j = 0; j <= m; j++)

            for(int k = 0; k <= s[i] && k * v[i] <= j; k++)

                dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i]] + k*w[i]);

}

优化版：（一维数组+二重循环）

　　二进制优化：对于每种物品，将其按2的次幂大小拆分合并，如s[i]=12时，方案为：第1个物品合并，第2~3个物品合并，第4~7个物品合并，第8~12个物品合并(1,2,4,5)。这样，就将多重背包问题转化成01背包问题

　　状态表示：dp[j]：在外循环的第i层时，表示从前i个物品中选择(每个物品只能选0或1个)且总体积不超过j的集合的最大价值，n层循环后(n为问题转化后的新n)，dp[m]就是最终答案

　　状态计算：dp[j] = max ( dp[j] , dp[j-v_i]+w_i )

　　核心代码：

int n, m;

int v[N], w[N], dp[M]; // N：maxn * logmaxs

void keyCode()

{

    int cnt = 0;

    for(int i = 1; i <= n; i++)

    {

        int a, b, s; // v_i, w_i, s_i

        cin >> a >> b >> s;

        int p = 1;

        while(p <= s)

        {

            cnt ++;

            v[cnt] = a * p, w[cnt] = b * p;

            s -= p, p *= 2;

        }

        if(s > 0)

        {

            cnt ++;

            v[cnt] = a * s, w[cnt] = b * s;

        }

    }

    n = cnt; // n --> 问题转化后的新n

    for(int i = 1; i <= n; i++)

        for(int j = m; j >= v[i]; j--) // 反向遍历

            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);

}

分组背包问题

朴素版：（二维数组）

　　状态表示：dp[i][j]：从前i组物品中选择(每组物品中只能选择0或1个)且总体积不超过j的集合的最大价值，则dp[n][m]就是最终答案

　　状态计算：dp[i][j] = max ( dp[i-1][j]，dp[i-1][j-v_i,1]+w_i,1，dp[i-1][j-v_i,2]+w_i,2，dp[i-1][j-v_i,3]+w_i,3，... )

　　核心代码：

int n, m; // n：物品数量, m：最大体积

int s[N], v[N][S], w[N][S];

int dp[N][M];

void keyCode()

{

    for(int i = 1; i <= n; i++)

    {

        for(int j = 0; j <= m; j++)

        {

            dp[i][j] = dp[i-1][j];

            for(int k = 1; k <= s[i]; k++)

                if(v[i][k] <= j)

                    dp[i][j] = max(dp[i][j], dp[i-1][j-v[i][k]] + w[i][k]);

        }

    }

}

空间优化版：（滚动数组，二维数组优化至一维）

int n, m; // n：物品数量, m：最大体积

int s[N], v[N][S], w[N][S];

int dp[M];

void keyCode()

{

    for(int i = 1; i <= n; i++)

    {

        for(int j = m; j >= 0; j--) // 反向遍历

        {

            for(int k = 1; k <= s[i]; k++)

                if(v[i][k] <= j)

                    dp[j] = max(dp[j], dp[j-v[i][k]] + w[i][k]);

        }

    }

}

巴特西

背包问题学习笔记 / Dynamic Programming（updating）

最新文章

热门文章