0-1 背包问题

发布于 2021-01-26 16:06:28   阅读量 57  点赞 0  

 经典的 0-1 背包问题描述如下:

给你一个可装载重量为 W 的背包和 N 个物品,其中第 i 个物品的重量为 wt[i],价值为 val[i],现在让你用这个背包装物品,最多能装的价值是多少。

 题目中的物品不可以分割,要么装进包里,要么不装。

 0-1 背包问题的状态有二:当前可选的物品n与当前的背包容量 w。(将当前可选的物品作为状态的原因是:随着背包容量的增大,总有新的物品要加入背包,通过递增当前可选物品以维护“已选物品”与未选物品的集合)。


474. 一和零

原题地址:https://leetcode-cn.com/problems/ones-and-zeroes/。

标签:【动态规划、【背包问题】、【状态压缩】

题目

 给你一个二进制字符串数组strs和两个整数mn

 请你找出并返回strs的最大子集的大小,该子集中 最多m个 0 和n个 1 。

 如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。


示例 1

输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出:4
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

示例 2

输入:strs = ["10", "0", "1"], m = 1, n = 1
输出:2
解释:最大的子集是 {"0", "1"} ,所以答案是 2 。

提示

  • 1 <= strs.length <= 600

  • 1 <= strs[i].length <= 100

  • strs[i] 仅由 '0' 和 '1' 组成

  • 1 <= m, n <= 100


解法

 这道是很典型的 0-1 背包问题。  感觉动态规划解题模板,本题的思路是:一点点增大容量(0 与 1 的个数),不断判断当前遍历到的物品(字符串),看是否要将其加到当前背包中(选择)。而选择的依据是:将当前字符串加进来后,字串的个数是否会增加。

定义状态:将子问题的状态定义为当'0'的容量为j,'1'的容量为k时,在可选字符串集合[0,i]上满足条件的最大子集大小,使用数组dp[i][j][k]表示。

状态转移方程:状态转移方程是选择的判断依据,本题中其为:

初始状态:为了避免对零值的分类讨论,通常多设置一行。


代码

void count0And1(string &str, int* result) {     // 计算当前字符串中 0 与 1 的个数
    result[0] = 0;
    result[1] = 0;

    for(char ch:str){
        if(ch=='0'){
            result[0]++;
        }else if(ch=='1'){
            result[1]++;
        }
    }
}

int findMaxForm(vector<string>& strs, int m, int n){
    int ***dpCache = new int** [strs.size()+1];
    for(int i=0; i<=strs.size(); i++){
        dpCache[i] = new int* [m+1];
        for(int j=0; j<=m; j++){
            dpCache[i][j] = new int[n+1];
            for(int k=0; k<=n; k++){
                dpCache[i][j][k] = 0;
            }
        }
    }

    int *count = new int[2];
    for(int i=1; i<=strs.size(); i++){
        count0And1(strs[i-1], count);
        for(int j=0; j<=m; j++){
            for(int k=0; k<=n; k++){
                dpCache[i][j][k] = dpCache[i-1][j][k];

                if(j>=count[0]&&k>=count[1]) {
                    if (dpCache[i - 1][j - count[0]][k - count[1]] + 1 > dpCache[i][j][k]) {
                        dpCache[i][j][k] = dpCache[i - 1][j - count[0]][k - count[1]] + 1;
                    }
                }
            }
        }
    }
    delete[] count;

    int result = dpCache[strs.size()][m][n];

    for(int i=0; i<=strs.size(); i++){
        for(int j=0; j<=m; j++){
            delete []dpCache[i][j];
        }
    }

    return result;
}


状态压缩

 由状态转移方程可知,其实解决每个当前问题时,只会用到dp[i-1]的子问题的解,即dp[i-n](n>2)的子问题的解都无意义,无需保存。

 于是我们可以降低状态数组的维度,即进行状态压缩。

 对于本题,仅交替使用两个二维数组dp[m][n]即可满足需求,从而降低算法的空间复杂度:

int findMaxForm(vector<string>& strs, int m, int n){
    int ***dpCache = new int** [2];
    int current = 0;    // 维护一个指针指向当前使用的数组

    for(int i=0; i<2; i++){
        dpCache[i] = new int* [m+1];
        for(int j=0; j<=m; j++){
            dpCache[i][j] = new int[n+1];
            for(int k=0; k<=n; k++){
                dpCache[i][j][k] = 0;
            }
        }
    }

    int *count = new int[2];
    for(int i=1; i<=strs.size(); i++, current++){
        count0And1(strs[i-1], count);
        for(int j=0; j<=m; j++){
            for(int k=0; k<=n; k++){
                dpCache[current%2][j][k] = dpCache[(current+1)%2][j][k];

                if(j>=count[0]&&k>=count[1]) {
                    if (dpCache[(current+1)%2][j - count[0]][k - count[1]] + 1 > dpCache[current%2][j][k]) {
                        dpCache[current%2][j][k] = dpCache[(current+1)%2][j - count[0]][k - count[1]] + 1;
                    }
                }
            }
        }
    }
    delete[] count;

    int result = dpCache[(current+1)%2][m][n];

    for(int i=0; i<2; i++){
        for(int j=0; j<=m; j++){
            delete []dpCache[i][j];
        }
    }

    return result;
}


Last Modified : 2021-01-28 20:03:05