昨天測試了一下，如何通過函數從程序的堆棧空間來申請空間供其他函數使用， 裡面提到了一個
數據結構的命題：背包問題。
命題如下：
View Code
/* 1.問題描述 假設有一個能裝入總體積為T的背包和n件體積分別為w1,w2,…wn的物品， 能否從n件物品中挑選若干件恰好裝滿背包，即使w1+w2+…+wm=T， 要求找出所有滿足上述條件的解。 例如： 當T=10，各件物品的體積{1,8,4,3,5,2}時，可找到下列4組解： (1,4,3,2) (1,4,5) (8,2) (3,5,2)。2.實現提示 可利用回溯法的設計思想來解決背包問題。首先，將物品排成一列，然後， 順序選取物品裝入背包，若已選取第i件物品後未滿，則繼續選取第i+1件， 若該件物品“太大”不能裝入，則棄之，繼續選取下一件，直至背包裝滿為止。 如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入的物品 “不合適”，應將它取出“棄之一邊”，繼續再從“它之後”的物品中選取，如此 重復，直到求得滿足條件的解，或者無解。 由於回溯求解的規則是“後進先出”，自然要用到“棧”。3.進一步考慮： 如果每件物品都有體積和價值，背包又有大小限制，求解背包中存放物 品總價值最大的問題解---最優解或近似最優解。*/
今天按照裡面的方法來進行測試，已經實現了部分代碼， 並且可以測試部分結果，但是還沒有完全實現，
現在將代碼貼出來供各位大俠點評，本來想今天弄出來的，但是因為明天要上班，同時今天下班有點晚（下班的
時候已經7點半了，）。
明天在繼續將剩下的部分實現。
View Code
/* 1.問題描述 假設有一個能裝入總體積為T的背包和n件體積分別為w1,w2,…wn的物品， 能否從n件物品中挑選若干件恰好裝滿背包，即使w1+w2+…+wm=T， 要求找出所有滿足上述條件的解。 例如： 當T=10，各件物品的體積{1,8,4,3,5,2}時，可找到下列4組解： (1,4,3,2) (1,4,5) (8,2) (3,5,2)。2.實現提示 可利用回溯法的設計思想來解決背包問題。首先，將物品排成一列，然後， 順序選取物品裝入背包，若已選取第i件物品後未滿，則繼續選取第i+1件， 若該件物品“太大”不能裝入，則棄之，繼續選取下一件，直至背包裝滿為止。 如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入的物品 “不合適”，應將它取出“棄之一邊”，繼續再從“它之後”的物品中選取，如此 重復，直到求得滿足條件的解，或者無解。 由於回溯求解的規則是“後進先出”，自然要用到“棧”。3.進一步考慮： 如果每件物品都有體積和價值，背包又有大小限制，求解背包中存放物 品總價值最大的問題解---最優解或近似最優解。
*/#include <stdio.h>
#include <stdlib.h>
struct node{
int sum;
int i;
};
typedef struct node NODE;
int getmemory(int **p,int size)
{
if(0 >= size) return NULL;
if(NULL == (*p=(int *)malloc(size * (sizeof(int)))))
return 0;
else
return 1;
}
int assignvalue( int *dest,int size)
{ if(NULL==dest)
return 0;
while(size>0)
{
scanf("%d",dest);
dest++;
size--;
}
return 1;
}
int solution(int *source,int volume, int size)
{
int i, j;
//j用來存儲相對棧首地址的便宜量 int *stack;
//申請的棧空間 int *header;
NODE temp;
if(NULL==source || 0==volume || 0==size) return 0; if(NULL==(stack=(int *)malloc(size*sizeof(int))))
return 0;
header=stack;
for(i=0;i<size;i++)
{
stack=header;
//每一次循環都使棧回到首地址 j=0;
//每一次循環都使棧的空間使用率為0；
temp.i=temp.sum=0;
//每一次循環都將使和以及空間計數值變為0；
//每次運算需要計算的次數， 第一次循環需要對size個值進行檢驗
//第二次循環則需要對size-i個值進行檢驗
while(temp.i <= size-i)
{
j++;
temp.sum += *(source+i+temp.i);
*stack=*(source+i+temp.i);
stack++;
if(temp.sum==volume)
//當求出來的和與容積大小相等時就輸出
{
while(j>0)
{
printf("%d ",*(stack-1));
j--;
stack--;
}
putchar('\n');
//輸出完畢就跳出循環，繼續對下一輪的數據進行求和
}
if(temp.sum < volume)
//如果取出的值加上後小於容積，則繼續取下一個值進行運算
{
temp.i++;
continue;
}
if(temp.sum > volume)
//如果取出來的值加上大於容積，則丟棄，同時將剛壓棧的數據出棧
{
temp.sum -= *(source+i+temp.i);
temp.i++;
*stack=0;
j--;
stack--;
continue;
}//end of if
}//end of while
}//end of for
free(stack);
free(header);
return 1;
}
int main(int argc, char *argv[]){
int size;
int volume;
int *number;
number=NULL;
printf("input the total number of the package:");
scanf("%d",&size);
printf("\nEnter the elements in the package:\n"); if(!getmemory(&number,size)) exit(1);
if(!assignvalue(number,size)) exit(1);
puts("\nPlease enter the volum of the package:");
scanf("%d",&volume);
if(0==solution(number,volume,size))
exit(1);
return 0;
}
現在的代碼還沒有考慮輸入、輸出的排版問題，等整個問題解決的時候再說吧...........
我發現有時候C語言還真有意思， 很容易實現一些有意思的問題。
上面的代碼還沒有完成，只是出具模型了， 以後慢慢弄點關於數據結構的命題來討論討論。
歡迎各位大俠彎腰找板磚............
