#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++;
}
}
//插入剩余的新生成元素
for(j=next-1;j capacity)
break;
ql[i].subResult[index].weight = ql[i-1].subResult[j].weight + Goods[i-1].weight;
ql[i].subResult[index].value = ql[i-1].subResult[j].value + Goods[i-1].value;
index++;
}
ql[i].end=index-1;
printf("i=%dn", i);
for(j=0;j=0;i--)
{
k=ql[i].end;
while (k>=0)
{
if (ql[i].subResult[k].weight>capacity)
k--;
else break;
}
j=k;
while (j>=0)
{
if (ql[i].subResult[j].weight+Goods[i].weight>capacity)
j--;
else break;
}
if (k>=0 j=ql[i].subResult[j].value+Goods[i].value)
printf("a[%d]=%dn", i, 0);
else
{
printf("a[%d]=%dn", i, 1);
capacity = capacity - Goods[i].weight;
}
}
}
}
int main()
{
goods Goods[] = {{2, 1}, {3, 2}, {4, 5}};
dknap(Goods, sizeof(Goods)/sizeof(Goods[0]), 6);
//goods Goods[] = {{100, 100}, {50, 50}, {20, 20}, {10, 10}, {7, 7}, {3, 3}};
//dknap(Goods, sizeof(Goods)/sizeof(Goods[0]), 165);
}
责任编辑：小草
