knapsack-problem

5열

2답변

배낭 변형 알고리즘 나는 자바에서 만들 수있는 다음과 같은 프로그램이 숙제로

: 우리가 K의 작가에 의해 손으로 복사 할 필요가 N 서의 스택을 책장에서. 각 책에는 Ui 페이지가 있으며, Ai는 책입니다. 각 작가에게 스택의 연속 된 책을 제공해야하며 책의 페이지를 분할 할 수 없습니다. 작가가 책을 제공하지만 작성자가 복사 할 수있는 최대 페이지 수를 최소화하여 프로그램을 만듭니다. 입력으로 사용자는 숫자 문자열을 제공합니다.

1열

1답변

균형 파티션 대 배낭 1/0 복잡도

균형 파티션 :. 0 ... K의 범위에있는 n 개의 정수 집합을가집니다.이 정수를 두 개의 하위 집합으로 분할하여 | S1 - S2 |를 최소화합니다. 여기서 S1과 S2는 두 개의 하위 집합 각각에있는 요소의 합계를 나타냅니다. 배낭 문제 : 각 가중치와 값이있는 항목 집합이 주어지면 총 가중치가 주어진 제한보다 작거나 같고 총 값이 큰 컬렉션에 포함

0열

2답변

곱셈을위한 배낭 알고리즘

나는 각 숫자에 약간의 비용이 첨부 된 숫자가 N이며, 문제는 가능한 모든 숫자 세트를 목록으로 선택하여 해당 제품이 특정 숫자 M보다 작고 비용의 합계. , [Solution 1 :- {(15, 85), (40, 60)} :- Product = 600 (which is less than, 1000), cost = 85 + 60 = 145] [Soluti

1열

1답변

동적 프로그래밍을 사용하여 배낭에서 항목 검색

동적 프로그래밍이 생소하고 처음으로 DP 문제를 시도했습니다. 문제는 성명서는 크기가 n이고 크기가 []이고 값이 [] 인 배낭이 배낭에 넣을 수있는 항목의 용량을 최대화합니다. 항목은 여러 번 반복 될 수 있습니다. (중복 된 항목이 허용됨). 내가 재발 관계를 수립하고, DP 테이블을 만들고, 결국 배낭에 넣어 수있는 최대 값을 얻을 수 있었지만, 나는

-1열

1답변

O (2^n * n) 배낭 알고리즘

배낭 문제에 대한 알고리즘 중 O (2^n * n) 개의 복잡도가있는 알고리즘은 무엇입니까? 나는 배낭 문제에 대한 해결책을 구현하도록 요청 받았습니다. 저는 프로그래밍에 익숙하지만 점근 표기법에 익숙하지 않습니다. 어느 알고리즘이 O (2^n * n) 개의 복잡도를 가졌는지 알 수 있습니까?

2열

1답변

다차원 부분 집합 합을위한 의사 다항식 또는 빠른 솔루션

다중/다목적 subset-sum problem에 대한 빠른 솔루션을 찾고 있습니다. 덧붙여서 (IMO를 계산하기 쉽도록 만드는) 추가 제한으로 합계에 포함 된 모든 값이 양수이고 모두 알려진 한계 값에 바인딩되어 있다고 가정 할 수 있습니다. 나는 O-NK pseudopolynomial 솔루션이 하나의 목적을 가진 부분 집합 합계 문제에 대해 알고있다. 나

0열

1답변

알고리즘은 배낭 알고리즘과 비슷합니다 (실제로는 아닙니다).

크기가 n 인 숫자 집합입니다 (n> 100이라고 가정). 하드 한계 x도 있습니다. 내가 원하는 것은 내 세트에서 가변 개수의 요소를 가져와 합계가 < = x이지만 가능하면 x에 가까워 지도록 이러한 요소의 조합을 찾는 것입니다. 분명히 나는 brute-force 접근 방식을 사용하고 싶지 않다. 효율적인 알고리즘이이 문제를 해결할 수 있는가?

7열

4답변

C++ 구현 배낭 분기 및 바인딩

분기 및 경계를 사용하여이 배낭 문제의 C++ 구현을 시도하고 있습니다. 여기에 본 웹 사이트의 자바 버전이 있습니다 : Implementing branch and bound for knapsack 내가 대신 내 C++ 버전은, 그러나 그것은 그 일을 아니에요해야한다는 (90)를 인쇄하기 위해 노력하고, 그것은 5. 합니까을 인쇄하는 것 누구는 그 문제가

0열

2답변

하스켈, 다른 유형의 목록의 목록을 가져 오는 중 오류 값 (FRAC 배낭 확률값)

지금까지 내가 가진 하스켈에서 분수 배낭 문제를 어떻게하려고 코드 : {- Input "how much can the knapsack hole <- x" "Possible items in sack [(label, value, weight), ...]" -} knap x [] = [] knap x y = if length y == 1 then 입력 목

0열

3답변

은 실제의 형태와 예상되는 유형`(T1, T2, T0)를 '일치 할 수 없습니다`[A0]`

I는 입력과 분수 배낭 문제를 해결하기 위해 노력하고있어, [("label 1", value, weight), ("label 2", value, weight), ...] 및 출력 , [("label 1", value, solution_weight), ("label 2", value, solution_weight), ...] 는하지만 computeKn