0
포지티브 가중치 (반드시 정수일 필요는 없습니다)와 해당 비용의 등 길이 (1xN) 목록이 주어지면 주어진 합계 S와 정확하게 합쳐지고 가장 낮은 비용을 갖는 가중치 목록 (가중치 목록의 하위 집합에 해당하는 비용 * 가중치의 합). 내가 다른 언어와 잘 맞지 않기 때문에 파이썬으로 작성하면 가능하다면 가능할 것입니다!가장 저렴한 비용의 합계와 같은 부분 집합을 찾는 알고리즘
예 :
이때 들어w = [2.5, 3.0, 1.0, 5.5] # Weight list
c = [1.0, 1.5, 2.0, 3.0] # Cost list
S = 6.5 # Target sum
우리 S에 가산 개의 가능한 서브 세트가 이러한 서브 세트
sub1 = [2.5, 3.0, 1.0]
sub2 = [1.0, 5.5]
비용은 다음 서브셋 1 이후
cost1 = 2.5*1.0+3.0*1.5+1.0*2.0 = 9.0
cost2 = 1.0*2.0+5.5*3.0 = 18.5
최저 비용 (9.0)이 내가 원하는 하위 집합입니다.
하나의 가능한 해결책은 물론 모든 가능한 조합을 계산 한 다음 계산 된 비용의 최소값을 선택하는 것입니다. 나는이 문제에 대한보다 효율적인 해결책이 있기를 바랬다.
다른 솔루션을 검색했지만 동일한 비용의 문제를 해결하고 동시에 비용이 가장 낮은 Python 솔루션을 찾을 수있었습니다. 다음은 그러한 솔루션의 예입니다. Algorithm to find which number in a list sum up to a certain number.
가중치는 최소한 긍정적입니까? 어쨌든 이것은 단일 항등 제약 조건을 갖는 매우 직설적 인 0-1 정수 선형 프로그래밍 문제입니다. 따라서 브랜치 - 바운드 알고리즘과 같은 것들이 가능할 것이다. 동적 인 프로그래밍은 확실히 자연스러운 방법입니다. 너 뭐 해봤 니? –
참고로이 문제는 부분 합계 문제 https://en.m.wikipedia.org/wiki/Subset_sum_problem로 알려져 있으며 효율적인 해결책이 존재하지 않는다고 널리 알려져 있습니다. (물론 당신은 효율적인 해결책을 요구하는 것이 아니라 단지 해결책입니다) – Cruncher
나는이 질문을 업데이트했다. 예, 가중치는 양의 값입니다. 나는 가능한 모든 조합을 검사하는 것보다 적어도 더 효율적인 것으로 기대하고 있습니다. – sheg