#include
#include
#include
//goods是一个或多个物品的重量和价值
typedef struct goods
{
int weight;
int value;
} goods;
//用来定义一个queryList数组
//数组中的每个元素定义一趟需要记录的数据
typedef struct queryList
{
goods *subResult; //一趟需要记录的数据
int end; //指示该趟数据的最后一个元素
} queryList;
queryList* dknap(goods *Goods, int count, int capacity)
{
int i, j, next, pre, index, k;
queryList *ql;
goods cur;
ql = (queryList *)malloc(sizeof(queryList)*count);
ql[0].subResult = (goods*)malloc(sizeof(goods));
ql[0].end = 0;
ql[0].subResult->weight = 0;
ql[0].subResult->value = 0;
for(i=1;iql[i-1].subResult[pre].weight)
if (cur.value = ql[i-1].subResult[pre].value) //抛弃旧元素
pre++;
else //插入新生成元素
{
ql[i].subResult[index].weight = cur.weight;
ql[i].subResult[index].value = cur.value;
index++;
cur.weight = ql[i-1].subResult[next].weight + Goods[i-1].weight;
cur.value = ql[i-1].subResult[next].value + Goods[i-1].value;
next++;
}
else
if (cur.value >= ql[i-1].subResult[pre].value) //抛弃旧元素
pre++;
else //抛弃新生成元素
{
cur.weight = ql[i-1].subResult[next].weight + Goods[i-1].weight;
cur.value = ql[i-1].subResult[next].value + Goods[i-1].value;
next++;
}
}
责任编辑：小草
