알고리즘 최적 채우기

Question

명확히하기 우리는 객체 목록을 가지고 있습니다. 각 개체에는 Size 특성과 Value 특성이 있습니다. 다음에는 제한된 공간이 있습니다.

공간을 차지하는 객체의 값이 가장 높은 잠재 가치를 가지도록 객체의 최상의 혼합을 얻는 방법을 알고 싶습니다.

크기가 값만큼 중요합니다. 그리고 크기와 값은 각 객체에 고정되어 있으므로 반 객체를 가질 수 없습니다.

예 그래서 우리는 우리가 10

의 그것의 크기의 개체 배치와 제한된 공간을 가지고

8 5 개체 B 크기 3과 가치와 크기 2과 가치와 객체 A를 가지고 우리는 Object A의 인스턴스와 Object B의 인스턴스 두 개를 가질 수있어 전체 값이 26이 될 수 있음을 알 수 있습니다.

개체 배열과 메서드를 사용하는 메서드/함수를 갖고 싶습니다. 크기가 크고 높이가 높은 객체의 배열을 반환합니다. 잠재적 가치.

처음부터 질문을 분명히하지 않으셔서 죄송합니다. 훌륭한 의견입니다. 위의 업데이트 된 질문을 통해 무엇을하려고하는지 명확히 알 수 있습니다.

Answer 1

처음 나타나는 점은 솔루션은 값의 수에 의존하지 않는다는 것입니다. 값을 고려하는 것으로 충분합니다.

def solve(values, target): 
    # Try big values first to get smaller results. 
    # Does not work in all cases. 
    # values.sort(reverse=True) 

    # Init an array with 0, -1, -1, ... 
    added_to_reach = [None] * (target + 1) 
    added_to_reach[0] = 0 

    # Dynamically calculate if it is possible to 
    # reach each value i up to target and store the 
    # last added value in added_to_reach[i]. 
    for i in range(1, target + 1): 
     for v in values: 
      if i - v >= 0 and added_to_reach[i-v] is not None: 
       added_to_reach[i] = v 

    # Calculate the solution by going back. 
    while added_to_reach[target] is None: 
     target -= 1 

    result = [] 
    while target > 0: 
     result.append(added_to_reach[target]) 
     target -= added_to_reach[target] 

    return result 

print(solve([5, 10, 13, 14], 39)) 

복잡성 target 선형이다

는 (예 {5, 8, 10, 15}) 소망 목표치은, 동적 프로그래밍을 사용하여이 값 집합이 주어 (표현 크기가 지수 함수적임). 우리가 다음에 시도 할 값을 탐욕스럽게 선택하면 큰 값을 먼저 시도하는 것이 좋을 수 있지만 실제로는 그렇지 않습니다 (예 참조).

Answer 2

N : 0 1 2 3
공간 : 1 2 3 4 5
값 : 사용자가 달성 할 수있는 3 내지 7 2 9
S = 10

후 최대의 효과는 항목을 0,1을 포함하여 19과 3은 9의 무게를 합친 것입니다.

/* * 
s = given limited space 
n = current element 
val = value array for each element 
space = space occupied by each element 
* */ 


public int findMaximumBenefit(int s, int n, int [] val, int [] space) 
{ 
    if (s == 0 || n == weight.length) 
    { 
     return 0; 
    } 

    // if this item's size is greater than space available 
    // then this item cannot be included in the knapsack 
    if (space[n] > s) 
     return findMaximumBenefit(s, n+1, val, space); 

    // Case1: maximum benefit possible by including current item in the knapsack 
    int includeCaseBenefit = val[n] + findMaximumBenefit(s-space[n], n+1, val, space); 

    // Case2: maximum benefit possible by excluding current item from the knapsack 
    int excludeCaseBenefit = findMaximumBenefit(s, n+1, val, space); 

    // return maximum of case1 and case2 values 
    return max(includeCaseBenefit, excludeCaseBenefit); 
} 

이 기능은 주어진 공간 제한으로 최대한의 이점을 제공합니다. 이제 당신은 모든 항목이 다음 아래 링크를 사용할 수있는 최대의 이익을 찾기 위해 공헌 한 어떤 알고 싶다면 http://www.ideserve.co.in/learn/dynamic-programming-0-1-knapsack-problem