我有一个关于显示使用过的数字的问题,我使用KnapSack算法,我想显示所有我使用过的最高值的数字。我在使用KnapSack算法,我想显示所有我用过的数字,以获得最高值。所以这是我的代码。
static int max(int a, int b)
{
int c = (a > b) ? a : b;
Console.WriteLine(c);
return (a > b) ? a : b;
}
// Returns the maximum value that can
// be put in a knapsack of capacity W
int knapSack(int[] r, int[] wt, int n, int W)
{
if (W < 0)
return Int32.MinValue;
if (n < 0 || W == 0)
return 0;
int include = r[n] + knapSack(r, wt, n, W - wt[n]);
int exclude = knapSack(r, wt, n - 1, W);
int V = max(include, exclude);
return V;
}
使用:
int[] r = new int[] { 3, 4, 8, 5, 6 };
int[] wt = new int[] { 2, 2, 3, 4, 7 };
int W = 11;
int z = W;
int n1 = r.Length;
stopwatch.Start();
int keik = knapSack(r, wt, n1 - 1, W);
stopwatch.Stop();
答案是28,但我需要显示所有的r数字,包括在这个数组中。我知道这个数组使用的数字是8 8 8和4,所以我需要以某种方式得到这些数字并显示到控制台。
你可以尝试让函数返回使用过的项目列表的方法。 你可以根据你的需要,返回项目值本身,或者返回值的索引。 我在这个例子中使用的是值。
下面是一个实现方式。
static int knapSack(int[] r, int[] wt, int n, int W, out List<int> list)
{
if (W < 0) {
list = new List<int>();
return Int32.MinValue;
}
if (n < 0 || W == 0) {
list = new List<int>();
return 0;
}
int include = r[n] + knapSack(r, wt, n, W - wt[n], out List<int> includedList);
int exclude = knapSack(r, wt, n - 1, W, out List<int> excludedList);
if (include > exclude) {
includedList.Add(r[n]);
list = includedList;
return include;
} else {
list = excludedList;
return exclude;
}
}
像这样调用
int keik = knapSack(r, wt, n1 - 1, W, out List<int> list);
Console.WriteLine(string.Join(",", list));
输出:
4,8,8,8