2016-11-02 3 views
-2

내 운동 해결에 문제가 있습니다. 동적 프로그래밍과 알고리즘에 대해 읽었을 때 제 운동이 "특정 배낭 문제"라고 생각합니다. 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)

+0

, 당신의 코드를 게시하시기 바랍니다, 당신이 직면하고 정확히 당신이 직면하고있는 문제가 된 오류. 보다 일반적인 가이드 라인을 보려면 [내 대답] (http://stackoverflow.com/a/40387517/2679529)을 살펴보십시오. –

+0

[특정 배낭 알고리즘]의 가능한 복제본 (http://stackoverflow.com/questions/40475287/specific-knapsack-algorithm) –

답변

0

을 몇 가지가 있습니다 인터넷에서 배낭 문제를 철저히 설명하는 좋은 자습서.

더 구체적으로 말하자면, 문제점과 DP 접근법이 완전히 설명 된 this specific one을 권장합니다. 여기에는 Java를 포함한 3 가지 언어로 된 솔루션이 포함됩니다.

// A Dynamic Programming based solution for 0-1 Knapsack problem 
class Knapsack 
{ 
    // A utility function that returns maximum of two integers 
    static int max(int a, int b) { return (a > b)? a : b; } 

    // Returns the maximum value that can be put in a knapsack of capacity W 
    static int knapSack(int W, int wt[], int val[], int n) 
    { 
     int i, w; 
    int K[][] = new int[n+1][W+1]; 

    // Build table K[][] in bottom up manner 
    for (i = 0; i <= n; i++) 
    { 
     for (w = 0; w <= W; w++) 
     { 
      if (i==0 || w==0) 
        K[i][w] = 0; 
      else if (wt[i-1] <= w) 
        K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); 
      else 
        K[i][w] = K[i-1][w]; 
     } 
     } 

     return K[n][W]; 
    } 

    // Driver program to test above function 
    public static void main(String args[]) 
    { 
     int val[] = new int[]{60, 100, 120}; 
     int wt[] = new int[]{10, 20, 30}; 
     int W = 50; 
     int n = val.length; 
     System.out.println(knapSack(W, wt, val, n)); 
    } 
} 
/*This code is contributed by Rajat Mishra */ 

출처 : GeeksForGeeks

+0

왜 아무도 나를 괴롭히지 않습니다. /이 기사를 읽었습니다. K 배열을 만들었지 만, 그렇지 않습니다. 도와주세요 ... – Zaroos77

+1

링크 만 응답은 링크가 작동하지 않는 경우 유용하지 않게되기 때문에 양질의 답변이 아닙니다. 귀하의 답변에 링크의 필수 세부 사항을 포함 시키십시오. –

+0

@AndyTurner 방금 내 대답을 편집했습니다. –