C#을 사용하여 배낭 문제 알고리즘을 작성하는 방법
배낭 문제(Knapsack Problem)는 주어진 용량과 일련의 항목이 있는 배낭을 설명하는 고전적인 조합 최적화 문제입니다. 각 항목은 고유한 값을 가지며 무게. 배낭의 용량을 초과하지 않으면서 배낭에 담긴 물품의 총 가치를 극대화하는 최적의 전략을 찾는 것이 목표입니다.
C#에서는 동적 프로그래밍 방법을 통해 배낭 문제를 해결할 수 있습니다. 구체적인 구현은 다음과 같습니다.
using System; namespace KnapsackProblem { class Program { static int Knapsack(int[] weights, int[] values, int capacity, int n) { int[,] dp = new int[n + 1, capacity + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= capacity; j++) { if (i == 0 || j == 0) dp[i, j] = 0; else if (weights[i - 1] <= j) dp[i, j] = Math.Max(values[i - 1] + dp[i - 1, j - weights[i - 1]], dp[i - 1, j]); else dp[i, j] = dp[i - 1, j]; } } return dp[n, capacity]; } static void Main(string[] args) { int[] weights = { 5, 3, 4, 2 }; int[] values = { 60, 50, 70, 30 }; int capacity = 8; int n = weights.Length; int maxValue = Knapsack(weights, values, capacity, n); Console.WriteLine("背包能装入的最大价值为:" + maxValue); } } }
위 코드에서는 항목 무게 배열 weights
와 항목 값 배열 를 받는 <code>Knapsack
이라는 정적 메서드를 정의했습니다. code>값, 배낭 용량 용량
및 항목 수 n
이 매개변수로 사용됩니다. 2차원 배열 dp
는 상태 전이 테이블을 표현하는 데 사용됩니다. dp[i, j]
는 첫 번째 i 중 배낭을 나타냅니다. code> 항목의 용량이 <code>j
일 때 로드할 수 있는 최대값입니다. Knapsack
的静态方法,它接收物品重量数组weights
、物品价值数组values
、背包容量capacity
和物品个数n
作为参数。方法中使用一个二维数组dp
来表示状态转移表,dp[i, j]
表示在前i
个物品中,背包容量为j
时能装入的最大价值。
然后,我们使用双层循环来填充状态转移表。如果i
或j
为0时,表示没有物品或背包容量为0,此时背包能装入的最大价值为0。如果物品i
的重量小于等于当前背包容量j
,则可以选择装入物品i
,也可以选择不装入物品i
,取二者中最大的值作为dp[i, j]
的值。如果物品i
的重量大于背包容量j
,则只能选择不装入物品i
。
最后,在Main
方法中我们定义了一个示例物品重量数组weights
、物品价值数组values
和背包容量capacity
,然后调用Knapsack
i
또는 j
가 0이면 아이템이 없거나 배낭 용량이 0이라는 뜻입니다. 이때 배낭에 넣을 수 있는 최대값은 0입니다. . i
항목의 무게가 현재 배낭 용량 j
보다 작거나 같은 경우 항목 i
를 로드하도록 선택할 수 있습니다. 항목 >i
를 로드하지 않도록 선택하고 둘 중 가장 큰 값을 dp[i, j]
의 값으로 사용합니다. i
항목의 무게가 배낭 용량 j
보다 큰 경우 i
항목을 로드하지 않도록 선택할 수 있습니다. 마지막으로 Main
메소드에서 예시 항목 무게 배열 weights
, 항목 값 배열 values
및 배낭 용량 capacity 를 입력한 후 <code>Knapsack
메서드를 호출하여 배낭에 싣을 수 있는 최대값을 계산하고 그 결과를 출력합니다. 🎜🎜위의 C# 코드 구현을 통해 배낭 문제를 쉽게 해결하고 최상의 패키징 솔루션을 얻을 수 있습니다. 물론 실제 응용 분야에서는 필요에 따라 알고리즘을 확장하고 최적화할 수도 있습니다. 🎜위 내용은 C#을 사용하여 배낭 문제 알고리즘을 작성하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!