내 운동 해결에 문제가 있습니다. 동적 프로그래밍과 알고리즘에 대해 읽었을 때 제 운동이 "특정 배낭 문제"라고 생각합니다. brute force 메서드로 해결했지만 동적 프로그래밍으로 해결할 수는 없습니다.어떻게 해결할 수 있습니까? KnapSack - 값은 동일하지만 서로 다른 객체에는 세 개의 가중치가 있습니다.
나는 300 톤의 무게를 가진 배 (배낭)를 가지고있다. 그 자체로 3 개의 물질 (X, Y, Z)을 가진 결정체가 있습니다 - 서로 다른 물질은 무게를 가지며 모든 결정체는 같은 값을가집니다. 가능한 한 많은 수의 결정체를 포장해야하지만 모든 포장 된 결정의 물질 비율은 1 : 1 : 1이어야합니다. 그러나 예를 들어 비율이 3 : 1 : 1 인 가장 큰 톤 수와 8 개의 결정 수의 비율이 같은 경우 (두 가지 다른 조합의 결정이 가장 많은 수의 톤을 제공함) 가장 낮은 수의 결정과의 조합.
나는 brute force 방법으로 해결 - 모든 조합의 배열 목록을 만들었습니다. 다음으로 나는 그것들이 1 : 1 : 1의 비율로 조합 된 것을 발견했다. 다음으로 가장 큰 수의 수를 제공하고 가장 큰 수의 수를 가진 조합을 찾았습니다 (동일한 수의 가장 큰 수의 조합이 두 개 이상있는 경우). 나는 테스트를 확인하고 좋은 점수를 반환했습니다. 동적 프로그래밍으로 어떻게 해결할 수 있는지 잘 모르겠습니다./저를 도와주는 사람이 있습니까?
예를 들어내가 10 명 결정이 :
1) X =2 Y =3 Z =4
2) X =5 Y=10 Z =2
3) X =3 Y =3 Z =3
4) X =1 Y =0 Z =6
5) X =9 Y=12 Z =4
6) X =1 Y =1 Z =1
7) X =2 Y =1 Z=0
8) X =1 Y =2 Z =3
9) X =1 Y =1 Z =1
10) X =4 Y =3 Z =3
솔루션은 다음과 같습니다 최대 27t 다섯 크리스탈 (번호 : 1, 3, 6, 7, 9)
, 당신의 코드를 게시하시기 바랍니다, 당신이 직면하고 정확히 당신이 직면하고있는 문제가 된 오류. 보다 일반적인 가이드 라인을 보려면 [내 대답] (http://stackoverflow.com/a/40387517/2679529)을 살펴보십시오. –
[특정 배낭 알고리즘]의 가능한 복제본 (http://stackoverflow.com/questions/40475287/specific-knapsack-algorithm) –