#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++;
　　}
　　}