题目描述

在计算机界中，我们总是追求用有限的资源获取最大的收益。

现在，假设你分别支配着 m 个0和 n 个1。另外，还有一个仅包含0和1字符串的数组。

你的任务是使用给定的m 个0和 n 个1，找到能拼出存在于数组中的字符串的最大数量。每个0和1至多被使用一次。

注意:

给定0和1的数量都不会超过100。

给定字符串数组的长度不会超过600。

示例 1:

输入:Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3输出:4解释:总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。

示例 2:

输入:Array = {"10", "0", "1"}, m = 1, n = 1输出:2解释:你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。

---

解题思路：典型的01背包问题，翻译后即将每个string视为一个物品，这个物品有两个value，value1为0的个数，value2为1的个数。开始时你有m个0和n个1，求最多能获取多少个物品。

最重要的是状态转移方程，这个题目有两个变量，0的个数和1的个数，所以创建一个二维数组，分别代表剩余num0个0和num1个1时可以获得的数目最多的物品。

dp[num0][num1]=max(dp[num0][num1],dp[num0-zeros][num1-ones]+1)

dp[m][n]中存的就是能买的最多的物品数。

注意
这里的二重for循环必须从m，n开始递减，而不能从0开始递增，因为每个物品只能买一次，若从0开始递增，dp[num0][num1]可以获得的是这次循环中更新过的dp[num0][num1],dp[num0-zeros][num1-ones]+1，相当于一个物品可以重复购买，变成了完全背包问题。
for(int num0=m;num0>=save[i][0];--num0)
for(int num1=n;num1>=save[i][1];--num1)

---

int findMaxForm(vector<string>& strs, int m, int n) {

    vector<vector<int>> save(strs.size(),vector<int> (2));

    for(int i=0;i<strs.size();++i)

    {

        for(int j=0;j<strs[i].size();++j)

        {

            if(strs[i][j]=='0')

                ++save[i][0];

            if(strs[i][j]=='1')

                ++save[i][1];

        }

    }

    vector<vector<int>> dp(m+1,vector<int> (n+1));

    for(int i=0;i<save.size();++i)

    {

        for(int num0=m;num0>=save[i][0];--num0)

            for(int num1=n;num1>=save[i][1];--num1)

            {

                dp[num0][num1]=max(dp[num0-save[i][0]][num1-save[i][1]]+1,dp[num0][num1]);

            }

    }

    return dp[m][n];

}