解题思路:
背包(即最终结果数组包含有m个0和n个1)容量有两个维度,m个0和n个1,最终结果含有的元素个数相当于物品个数。
由于每个物品只能使用1次,所以这依然是个01背包问题。本题是求解装满这个背包最多有多少个物品。
dp数组含义:dp[i][j]表示在i个0,j个1的情况下,最多背dp[i][j]个物品,最后结果是dp[m][n].
递推公式:dp[i][j] = max(dp[i-x][j-y] + 1,dp[i][j])
初始化:dp[0][0] = 0,非0下标初始化成0(由递推公式得)
遍历顺序:先物品再背包(倒序),这里背包容量是二维的。
代码实现: