[알고리즘] 클래스 가방 문제 해결 조합 수 및 자바 구현
1394 단어 leetcode
정수 n 을 정 하고 1 에서 n 의 정 수 를 몇 개 취하 면 정수 m 와 같 을 수 있 으 며 프로 그래 밍 은 모든 조합의 개 수 를 구 할 수 있 습 니 다.예 를 들 어 n = 6, m = 8 일 때 네 가지 조합 이 있다. [2, 6], [3, 5], [1,2,5], [1,3,4]。n 과 m 를 120 보다 작 게 한정 하 다. 입력 설명: 정수 n 과 m
출력 설명: m 와 같은 모든 조합의 개 수 를 구하 다.
입력 예 1: 6 8
출력 예 1: 4
우선 이것 은 동태 적 인 계획 문제 로 가방 문제 와 유사 하 다. 다른 것 은 모든 수의 가중치 가 바로 그 자체 이 고 마지막 으로 구 한 결 과 는 조합의 개수 이지 조합의 방법 이 아니다.다음 과 같은 몇 가지 상황 으로 나 뉜 다.
1. n < 1 또는 m < 1 시 조합 수가 없습니다.
2. n = m 일 때 지금 안정 적 인 조합 방법 은 n = m 이다.
3. n > m 일 때 숫자 가 m 보다 큰 조합 은 존재 하지 않 는 다. 예 를 들 어 m = 4, n = 6. 그러면 5, 6, 두 배열 은 조합 에 나타 날 수 없 기 때문에 n = m 는 f (4, 4) 의 개 수 를 계산 하면 된다.
4. n < = m 일 때 용량 이 m 인 가방 에 숫자 를 채 웠 습 니 다. n = m 가 (2) 있 기 때 문 입 니 다. 중 안정 에는 조합 방식 이 존재 한다.그래서 n 만 계산 하면
V(n, m)=max{V(n-1, m-n)+Vi，V(n-1, m)}
자바 구현 코드 는 다음 과 같 습 니 다:
public class bag01_question {
public int bag(int n ,int m) {
if(n==0||m==0)
return 0;
if(n>m)
n=m;
int sum = 0;
if(m==n)
sum++;
sum+= bag(n-1,m);
sum+= bag (n-1,m-n);
return sum;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner ms = new Scanner(System.in);
int n = ms.nextInt();
int m = ms.nextInt();
int mo = new bag01_question().bag(n,m);
System.out.println(mo);
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
