알고리즘 (내가 예와 함께 설명 할 것이다) 나는 때라도 문제를 해결하는 알고리즘을 찾고 있어요

Question

특정 양의 최고의 피팅 요소를 찾을 수 있습니다 :

하자 내가 10.000 $가 있다고 가능 금액과 다음 비용을

비용 : 1 : 1.000 $

비용 2 : 3.000 $

비용 3 : 4.000 $

비용 4 : 5 나는 내 양을 사용하여 재정 수 .000 $

부분적으로 비용을 지불 할 수 없으므로 전체 비용을 지불하거나 전혀 지불하지 않습니다. 내가 찾고있는 것은 사용 가능한 양을 초과하지 않을 비용의 조합을 찾는데 도움이되는 알고리즘이지만, 다른 쪽에서는 대부분 또는 전체 사용 가능한 양을 사용합니다. 내 예에서

은 다음과 같습니다 비용 1 + 3 + 내가 많은 비용을 최대한 조달 할 수있는 방법을 결정하는 매개 변수를 추가 할 수도 싶습니다 4.

비용을 비용. 위의 예에서 두 가지 비용 만 지불 할 수 있다고 말하면 비용 3과 비용 4가 반환됩니다.

내 접근 방식은 사용 가능한 모든 조합을 확인하고 합계하여 사용 가능한 양을 가장 잘 사용하는 것을 선택하는 것입니다. 그러나 최적의 조합을 찾는 가장 간단한 방법이 있는지 궁금합니다.

Answer 1

예산을 모두 소진 할 때까지 목록을 정렬하고 상단을 선택할 수 있습니다. 또한 빈 포장에 사용되며 최적의 범위 내에 있음을 보증합니다.

Answer 2

일반적인 데이터에 대한 솔루션을 향상시킬 수는 없지만 속도를 향상시킬 수있는 몇 가지 개선 사항이 있습니다.

총량 N 간단한 동적 솔루션이 매우 낮은 경우 :

setOfValues 
put totalAmount to setOfValues 
foreach cost do 
    foreach amount in setOfValues do 
     if (amount - cost) > 0 and not exists (amount - cost) in setOfValues 
      put (amount - cost) to setOfValues 
get lowest setOfValues 

당신은 간단하게는 (최대 x에 대한 비용 등) 추가 요구 사항으로 업그레이드 할 수 있습니다가.

Answer 3

몇 주 전에 java에서 이와 같은 알고리즘을 설계했습니다. 폭 N 인 이진 행렬을 사용했습니다. 여기서 N은 다른 비용의 수이고, 높이는 2^N이되어 모든 가능한 조합을 제공합니다.

첫 번째 항목은 가장 낮은 비용을 나타냅니다. 여기에 1000 예입니다, 3000, 4000 (이 작업을 확장 할 수 있습니다,하지만 난 그냥 내가 한 방법을 알려 드리려고합니다.)

폭 = N = 3

높이 = 2^N = 8

을

0 0 0 = 0  + 0  + 0  = 0 
1 0 0 = 1000 + 0  + 0  = 1000 
0 1 0 = 0  + 3000 + 0  = 3000 
1 1 0 = 1000 + 3000 + 0  = 4000 
0 0 1 = 0  + 0  + 4000 = 4000 
1 0 1 = 1000 + 0  + 4000 = 5000 
0 1 1 = 0  + 3000 + 4000 = 7000 
1 1 1 = 1000 + 3000 + 4000 = 8000 

비용이있는 목록이 있습니다. 행렬별로 행렬을 내려 가면서 행렬에 1이있는 목록을 확인했습니다. 비용이 분류되기 때문에 전체 행보다 같거나 큰 행을 찾을 수 있습니다.

당신이 이해하지 못하면 내가 정교하게 말해줘!

Answer 4

문제는 NP problem입니다. 허용 가능한 시간 프레임 내에서 최적의 솔루션을 찾도록 보장 할이 문제에 대한 알려진 해결책이 없습니다. 최적의 솔루션을 찾는 유일한 방법은 가능한 모든 솔루션을 시도한 다음 어느 솔루션이 최적인지 확인하는 것입니다. 하지만 수천 개의 비용이있는 경우 이는 매우 느립니다.

위에서 언급 한 단순한 접근 방식보다 빠른 다른 모든 솔루션이 최적의 솔루션을 찾지 못할 수도 있습니다. 그들은 좋은 해결책을 찾을 수 있지만, 더 나은 해결책이 가능했는지 여부는 말할 수 없습니다.

다음과 같은 문제가 있습니다. X 파운드의 물품을 운송 할 수있는 트럭이 있고 다른 무게의 물건이 있습니다. 목표는 사용 가능한 용량을 최적으로 사용하는 것입니다. 이것은 "배낭 문제"라고도합니다. this page에 나열된 솔루션 이외에 더 좋은 솔루션은 없습니다. 그러나 그들 중 누구도 최적의 결과를 보장 할 수는 없습니다.

Answer 5

이것은 간단한 동적 프로그래밍 문제 (변형의 배낭)입니다. 상태는 [위치] [rest_amount] [how_many_bills_can_be_paid]로 정의 할 수 있습니다. 아래 재귀 용액 :

가 C 가정 비용의 배열이며 memo -1로 초기화된다

const int N = 10; //number of notes to pay 
int memo[N][M][K]; //remember to initialize it with -1 

int func(int cur_index,int rest_amount,int K){ 

    if(cur_index == N){ 
     return 0; 
    } 

    int &ret = memo[cur_index][rest_amount][K]; 
    if(ret != -1) return ret; //memoization ensures we won't solve the same sub problem more than once 
    ret = 0; 
    if(rest_amount >= C[cur_index] && K > 0) 
    ret = func(cur_index+1,cost+C[cur_index],K-1); 

    ret = max(ret,func(cur_index+1,cost,K); 

    return ret; 
}