Ones and Zeroes 1 과 0

컴퓨터 업계 에서 우 리 는 항상 유한 한 자원 으로 가장 큰 수익 을 얻 는 것 을 추구한다.
지금,네가 각각 지배 하고 있다 고 가정 해라. 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 가방 의 변형 판 입 니 다.약간 다른 것 은 우리 의 용량 이 m 와 n 으로 바 뀌 었 습 니 다.그 중에서 m 는 남 은 0 의 개 수 를 나타 내 고 n 은 남 은 1 의 개 수 를 나타 내 며 우 리 는 유독 2 차원 으로 줄 이 고 전달 공식 은 다음 과 같 습 니 다.

dp[p][q] = max(dp[p][q], dp[p - result[0]][q - result[1]]+1);

그 중에서 dp 는 길이 가 m*n 인 2 차원 배열 로 그 중에서 dp[m][n]은 m 개 0 과 n 개 1 시의 최 적 화 를 나타 낸다.여기 서 한 마디 더 하고 공간 최 적 화 를 하지 않 는 전달 공식 은 다음 과 같다.

dp[i][p][q] = max(dp[i-1][p][q], dp[i-1][p - result[0]][q - result[1]]+1);

그 중에서 dp[i][p][q]는 첫 번 째 요소 부터 i 번 째 요소 까지 가방 용량 이 p 개 0 과 q 개 1 이 남 았 을 때의 최 적 화 를 나타 낸다.여기 서 모든 상품 의 가 치 는 1 이 므 로 우리 의 목 표 는 모든 상품 중에서 일부 상품 을 선택 하여 가방 용량 p 와 q 를 초과 하지 않 는 상황 에서 가 치 를 최대 로 하 는 것 이다.이것 은 3 차원 배열 이다.우 리 는 그것 을 2 차원 배열 로 최적화 시 켰 다.위의 공식 과 같다.
참조 코드 는 다음 과 같 습 니 다.

class Solution {
public:
vector count(string &s) {
	if (s.size() == 0) {
		return { 0,0 };
	}
	int sum_zero = 0;
	int sum_one = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '0') {
			sum_zero++;
		}
		else {
			sum_one++;
		}
	}
	return { sum_zero,sum_one };
}
int findMaxForm(vector& strs, int m, int n) {
	int len = strs.size();
	int res = 0;
	if (len == 0) {
		return 0;
	}
	int **dp = new int *[m + 1];
	for (int i = 0; i < m + 1; i++) {
		dp[i] = new int[n + 1];
	}
	for (int i = 0; i < m + 1; i++) {
		for (int j = 0; j < n + 1; j++) {
			dp[i][j] = 0;
		}
	}
	for (int i = 0; i < len; i++) {
		for (int p = m; p >= 0; p--) {
			for (int q = n; q >= 0; q--) {
				vector result = count(strs[i]);
				if (p >= result[0] && q >= result[1]) {
					dp[p][q] = max(dp[p][q], dp[p - result[0]][q - result[1]]+1);
				}
			}
		}
	}
	res = dp[m][n];
	for (int i = 0; i < m + 1; i++) {
		delete[] dp[i];
	}
	delete[] dp;
	return res;
}
};

컴퓨터 업계 에서 우 리 는 항상 유한 한 자원 으로 가장 큰 수익 을 얻 는 것 을 추구한다.
지금,네가 각각 지배 하고 있다 고 가정 해라. 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" 。