CSharp 实现0-1-knapsack背包问题 源代码
时间: 2023-10-22 14:10:59 浏览: 51
很好,这是一个计算机科学问题。以下是 CSharp 实现 0-1-knapsack 背包问题的源代码:
```
using System;
using System.Collections.Generic;
public class Knapsack
{
public int MaxValue(int[] weights, int[] values, int capacity)
{
int[,] dp = new int[weights.Length + 1, capacity + 1];
for (int i = 1; i <= weights.Length; i++)
{
for (int j = 1; j <= capacity; j++)
{
if (weights[i - 1] > j)
{
dp[i, j] = dp[i - 1, j];
}
else
{
dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[weights.Length, capacity];
}
}
// Test
public class Test
{
public static void Main()
{
int[] weights = new int[] { 10, 20, 30 };
int[] values = new int[] { 60, 100, 120 };
int capacity = 50;
Knapsack ks = new Knapsack();
int result = ks.MaxValue(weights, values, capacity);
Console.WriteLine("Maximum value: " + result);
}
}
```
希望这个代码对你有所帮助!