있습니다찾기 저렴한 방법은 다른 상점에서 아이템을 구입하지만, 상점 그래서 문제 다음 한 한 시간 요금
k 저장하고 n 항목이 있습니다. 모든 상점은이 품목들을 다른 가격으로 가질 수 있습니다 (또한 모든 품목을 보유하지 않은 상점이 있음). 그러나 특정 상점에서 구매하려는 경우 일회성 요금을 지불해야하며, 이는 모든 상점마다 다릅니다. 모든 항목을 구입하는 가장 저렴한 방법을 찾는 방법?
내가 지금 가지고있는 유일한 해결책은 가능한 모든 상점 조합을 시도하고 가장 저렴한 것을 찾으라는 것입니다. 더 나은 방법이나 추론적인 근사가 있습니까?
이 문제에 대해 3-SAT를 상당히 간단하게 줄일 수 있으므로 NP- 하드 (각 변수에 대한 저장소를 소개하고 각 변수의 보수를 위해 일회성 요금 1을 입력 한 다음 변수 및 보완 저장소에서 모두 판매되는 각 변수에 대한 특별 항목뿐만 아니라 모든 0을 계산하고 가격이 k 인 모든 항목을 구입할 수 있는지 확인하십시오. 따라서 brute-force 검색보다 더 나은 복잡성으로 최적의 결과를 생성하는 알고리즘의 의미에서 "더 나은 방법"이 될 수는 없습니다.
시뮬레이션 어닐링은 여기에서 잘 작동한다고 생각합니다. 각 어닐링 단계에서 상점을 추가 또는 제거한 다음 해당 상점 선택에 대해 가장 낮은 비용을 찾습니다.
integer linear program으로 모델링 할 수 있습니다.
상수 : 는 F[j]가 저장 J를 입력하는 수수료하자, P[i][j] 매장 j에서 항목 i의 가격을하자, 그리고 W[i] 당신이 살 필요 항목 i의 숫자가 될 수 있습니다. K을 큰 상수 (max_{i}(W[i])보다 큼)로 지정하십시오.
변수 : N[i][j]은 j 상점에서 구입하는 i 품목 수입니다. C[j]은 상점 j에서 아무것도 구입하지 않은 경우 1이되고, 그렇지 않은 경우 0이됩니다.
그런 다음 최소화하려는 품목은 sum_{i,j}(P[i][j]*N[i][j]) + sum_{j}(F[j]*C[j])입니다. 즉, 구매 한 물량과 입력 한 상점의 상점 비용으로 제품 가격을 최소화하고자합니다.
주제에 대한 모든 i, sum_{j}(N[i][j]) = W[i]에 대한 모든 i 및 j, C[j]*K >= N[i][j]합니다. 즉, 구입 한 품목 수량의 합계가 원래 원하는 값이고 의 경우 N[i][j]이 0이 아닌 경우 C[j]은 0이 아니어야합니다.
모든 변수는 양수이고 정수 여야합니다.
목적 함수 (즉, 최소화하려고하는 것)와 "subject to"단락의 각 조건은 문제의 변수에서 선형입니다.
즉시 문제를 해결할 수 있습니다 : ILP 솔버에 연결하십시오 (예 : GLPK). 적용 할 수있는 이러한 문제를 해결하기위한 근사 및 추론에 대한 이론적 결과가 있습니다.예를 들어 선형 프로그램으로 해결할 수 있습니다 (즉, 양이 정수가 아닌 실수 값이 될 수 있도록 문제를 완화 한 다음) 가장 가까운 가능한 정수 값 솔루션을 선택하십시오.
모든 점수에 입장료가 부과 되었습니까? – Lrrr
네, 정확히 말하면, 특정 상점에서 물건을 사고 싶다면 얼마나 많은 물건을 살든지간에 수수료를 지불해야합니다. – piotros