动态规划求0/1背包问题

　　#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;[NextPage] 　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++;

　　}

　　}

　　//插入剩余的新生成元素

[NextPage]

　　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;

　　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;

[NextPage]

　　}

　　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);

　　}