Question

C语言 一段代码看不懂 求教

0-1背包问题：给定n中物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C.问：如何选择装入背包的物品，使得装入背包中物品的总价值最大？

kua的解法：
本来用动态规划的方法效率更高，但是为了熟悉子集树的选取问题，就用回溯了

0-1背包问题实际上是子集选取问题，即选取一个x={k,k,k,k...k) (k= 0或1)向量的自己
回溯法的方法是遍历所有子集可能性，中间用剪枝函数取出明显不符合结果的节点

class Knapsack
{
static int C = 70; //背包容量
static int n = 4;
static int[] w = new int[n];
static int[] v = new int[n];
static int maxV = 0;
static int sumW = 0;
static int sumV = 0;
static int[] x = new int[n]; //当前解
static int[] maxX = new int[n]; //最优解
public static void main(String[] args)
{
w[0] = 30;
v[0] = 6;
w[1] = 21;
v[1] = 3;
w[2] = 29;
v[2] = 9;
w[3] = 24;
v[3] = 7;
Knapsack.backtrack(0);
System.out.println(Knapsack.maxV);
for(int i = 0; i < Knapsack.n; i++)
System.out.print(Knapsack.maxX[i] + " ");
}

public static void backtrack(int t)
{
if( t > n - 1)
{
if( sumV > maxV )
{
maxV = sumV;
for(int i = 0; i < n; i++)
maxX[i] = x[i];
}
return;
}
for(int i = 0; i <= 1; i++)
{
x[t] = i;
sumW += w[t] * i;
sumV += v[t] * i;
if(sumW < C)
backtrack(t + 1);
sumV -= v[t] * i;
sumW -= w[t] * i;
}

}

}

上面那段public static void backtrack(int t)的函数没有看懂 求教

Answer 1

long
filesize(FILE
*stream)
{
long
curpos,
length;
curpos
=
ftell(stream);
//
获取文件指针的位置
fseek(stream,
0L,
SEEK_END);
//
将文件指针移到文件末尾
length
=
ftell(stream);
//获取文件当前指针的位置。
fseek(stream,
curpos,
SEEK_SET);
//将文件指针移到curpos处
return
length;
}

Answer 2

这个表示函数中变量全部为全局变量，不随函数结束而清零，即v、w这些变量的值在下一次调用或别的函数中调用的时候会继续累加。

Answer 3

去精锐找人问问吧 或者找一些技术群 都可以