-1
배낭 문제에 대한 매우 간단한 욕심 많은 알고리즘을 쓰려고합니다. 입력은 두 개의 병렬 배열입니다. 하나의 배열은 항목의 값을 포함하고 다른 배열은 가중치를 포함합니다.자바에서 배낭에 대한 욕심 많은 알고리즘
내가 쓰려고하는 욕심 많은 알고리즘은 다음과 같이 진행됩니다. 가장 높은 값을 가진 항목을 확인하고이를 배낭에 넣습니다. 그런 다음이 항목의 값을 0으로 설정하십시오. 어떤 항목이 가장 높은 가치를 지니고 있는지 다시 확인하고 배낭에 아직 보관할 수있는 경우 배낭에 넣으십시오. 유지할 수 있으면 값을 다시 0으로 설정하고 (입력 한 후) 가장 높은 값을 다시 찾습니다. 그 배낭이 더 이상 붙잡을 수 없다면 프로그램을 끝내십시오.
나는 거기에 더 많은 욕심 많은 알고리즘이 있다는 것을 알고 있지만, 이것은 꽤 단순한 것으로 보인다. 나는 이것을 관리 할 수 있다고 생각한다. 내 문제는 최대 값을 찾으려면 전체 값 배열을 거쳐야한다는 것입니다. 그런 다음 그것을 찾았을 때 그것을 배낭에 넣고 값을 0으로 설정했습니다. 그러나 문제는 그 다음에 for 루프로 돌아가 새로운 가장 높은 가치의 아이템을 찾아 배낭에 넣어야한다는 것입니다. 그러나 나는 이것을 어떻게 할 것인지 모른다.
저는 자바로 이것을 작성하고 있습니다.
응답 해 주셔서 감사합니다. 나는 욕심 많은 알고리즘을 사용하여 배낭을 풀 수있는 여러 가지 방법이 있으며, 이미 값/무게의 비율이 가장 높은 배낭을보고 사용했음을 압니다. 저는 처음부터 완전히 초보자로서 프로그래밍을 연습하기 위해 모든 다른 종류의 것을 시도하고 싶었습니다. 먼저 정렬 한 다음 문제가 반복되는 것은 내 체중 인덱스가 내 값 인덱스와 더 이상 일치하지 않아서 더 이상 배낭 안에 들어 있는지 더 이상 확인할 수 없다는 것입니다. 나는 이것이 내가이 문제를 해결할 수있는 방법 일 것이라고 생각했다. – Tezen
가중치와 값 사이에는 일치가 있습니다 (즉, 임의로 재 배열 될 수 없음). 현재는 가중치와 값을 별도의 배열에 저장하고 해당 순서를 순 서적으로 적용하려고하는 것처럼 들립니다. 아이템의 가치/무게를 유지하는 간단한 클래스를 작성함으로써 정보를 캡슐화 할 수 있습니다. 그런 다음 어떤 가중치와 값이 함께 속하는지 수동으로 추적하지 않고 해당 객체의 배열을 만들고 정렬 할 수 있습니다. –