第一篇：0-1背包問題思路
0-1背包問題通用算法：（算是非貪心算法吧，當然也用到貪心思想，每次取最大值）
1.假設：
n種物品，種類1,2,…,n;每種物品質量m[0],m[1],m[2],…,m[n-1];每種物品價值v[0],v[1],…,v[n-1];背包能承受的總質量為mk，設數(shù)組dp[1],dp[2],…,dp[mk-1],dp[mk]（注意，dp不包含0包含mk）表示當包內(nèi)放了1,2,…,mk-1,mk質量的東西時能達到的最大價值。
2.問題：
如何安排放置在背包里的物品使得背包內(nèi)物品總價值能達到最大？（假設每種類型物品個數(shù)是無限的）
3.算法：
第一步：將n種物品按照質量從小到大排序，相應的價值也要跟著質量數(shù)組m的變化而變化，保持對應關系。
第二步：按照如下算法進行
for(i = 0;i < n;++i)
{
for(j = m[i];j <= mk;++j){} dp[j] = max{ dp[j] , dp[j-m[i]] + v[i] };
}
最終執(zhí)行完畢后，dp[mk]值即為包內(nèi)放置mk質量的東西時能達到的最大價值的值！
4.特例：
當題目只給你質量而沒有價值時，不放設價值和質量取相同值，轉化為特殊的0-1背包問題，如上解問題。當題目只給你價值而沒有質量時也不妨設質量和價值取相同值，同樣用上述方法解決問題。
5.思路： 用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}?？梢詨嚎s空間，f[v]=max{f[v],f[v-c[i]]+w[i]}
第二篇：c語言版背包問題
#include
int c[10][100];/*對應每種情況的最大價值*/
int knapsack(int m,int n){
int i,j,w[10],p[10];
printf(“請輸入每個物品的重量,價值：n”);
for(i=1;i<=n;i++)
scanf(“%d,%d”,&w[i],&p[i]);
for(i=0;i<10;i++)
for(j=0;j<100;j++)
c[i][j]=0;/*初始化數(shù)組*/
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(w[i]<=j)/*如果當前物品的容量小于背包容量*/
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
/*如果本物品的價值加上背包剩下的空間能放的物品的價值*/
/*大于上一次選擇的最佳方案則更新c[i][j]*/
c[i][j]=p[i]+c[i-1][j-w[i]];
else
c[i][j]=c[i-1][j];
}
else c[i][j]=c[i-1][j];
}
return(c[n][m]);
}
int main(){
int m,n;int i,j;
printf(“請輸入背包的承重量,物品的總個數(shù)：n”);
scanf(“%d,%d”,&m,&n);
printf(“旅行者背包能裝的最大總價值為%d”,knapsack(m,n));
printf(“n”);
return 0;}
第三篇：0-1背包問題c語言程序
0-1背包問題
問題描述
給定n種物品和一背包，物品i的重量是wi，其價值是pi，背包的容量是M，如何選擇裝入背包中的物品總價值最大？ 問題分析
記c[i][m] 表示前i個物品，在背包容量大小為m的情況下，最大的裝載量。如果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為m的背包中”，價值為c[i-1][m]；如果放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的容量為m-w[i]的背包中”，此時能獲得的最大價值就是c[i-1][m-w[i]]再加上通過放入第i件物品獲得的價值p[i]。因為背包最大容量M未知。所以，我們的程序要從1到M一個一個的試。比如，開始任選N件物品的一個?？磳狹的背包，能不能放進去，如果能放進去，并且還有多的空間，則多出來的空間里能放N-1物品中的最大價值。從以上最大價值的構造過程中可以看出： c(n,m)=max{c(n-1,m), c(n-1,m-w[n])+p(n)其中c[i-1][m] 表示第i件物品不裝入背包中，而c[i-1][m-w[i]] + p[i] 表示第i件物品裝入背包中。偽代碼：
1.最優(yōu)值max(x1*p1+x2*p2+??xn*pn)int knapsack(int m,int n,int *w,int *p){
bool a;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(w[i]<=j)
{
a=p[i]+c[i-1][j-w[i]]>c[i-1][j];
c[i][j]=a?p[i]+c[i-1][j-w[i]]:c[i-1][j];
//前者表示放i物品，后者表示不放i物品
}
else //i號物品重量大于剩余容量，不能再放i號物品
c[i][j]=c[i-1][j];
}
return(c[n][m]);//最后的值即為最優(yōu)值，返回主函數(shù) }
2.求最優(yōu)n元0-1向量(x1,x2,x3??,xn)int getbest(int m,int n,int *w,int *p){
if(n==0)return 0;//遞歸，每次遞歸n減1，n為0時退出
if(w[n]>m)
{
x[n]=0;
getbest(m,n-1,w,p);
}
else
{
//如果c[n][m]由p[n]+c[n-1][m-w[n]]而來,則x[n]=1;
//如果c[n][m]由c[n-1][m]]而來,則x[n]=0;
x[n]=c[n-1][m]<=p[n]+c[n-1][m-w[n]];
if(x[n])
getbest(m-w[n],n-1,w,p);
else
getbest(m,n-1,w,p);
} }
程序：
#include
bool a;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(w[i]<=j)
{
a=p[i]+c[i-1][j-w[i]]>c[i-1][j];
c[i][j]=a?p[i]+c[i-1][j-w[i]]:c[i-1][j];
//前者表示放i物品，后者表示不放i物品
}
else //i號物品重量大于剩余容量，不能再放i號物品
c[i][j]=c[i-1][j];
}
return(c[n][m]);//最后的值即為最優(yōu)值，返回主函數(shù) }
//求最優(yōu)n元0-1向量(x1,x2,x3……,xn)int getbest(int m,int n,int *w,int *p){
if(n==0)return 0;//遞歸，每次遞歸n減1，n為0時退出
if(w[n]>m)
{
x[n]=0;
getbest(m,n-1,w,p);
}
else
{
//如果c[n][m]由p[n]+c[n-1][m-w[n]]而來,則x[n]=1;
//如果c[n][m]由c[n-1][m]]而來,則x[n]=0;
x[n]=c[n-1][m]<=p[n]+c[n-1][m-w[n]];
if(x[n])
getbest(m-w[n],n-1,w,p);
else
getbest(m,n-1,w,p);
} }
void main(){
int m,n;int *w=NULL;
int *p=NULL;
printf(“輸入背包容量和貨物個數(shù)：”);
scanf(“%d%d”,&m,&n);p=(int *)calloc(n,sizeof(int));//分配n*sizeof(int)的內(nèi)存大小，存取n個物品的價格
w=(int *)calloc(n,sizeof(int));//分配n*sizeof(int)的內(nèi)存大小，存取n個物品的質量
if(!p||!w)//檢測分配是否成功
{
printf(“Not Enough Memory!n”);
exit(1);//分配失敗，退出
}
for(int i=1;i printf(“物品x%d的重量和價值：”,i); scanf(“%d%d”,w+i,p+i);} printf(“n總價值最大為：%d”,knapsack(m,n,w,p)); printf(“n”); for(i=0;i<=n;i++)//打印執(zhí)行動態(tài)規(guī)劃每步的值 for(int j=0;j<=m;j++) { printf(“%3d ”,c[i][j]); if(j==m) printf(“n”); } getbest(m,n,w,p); printf(“最優(yōu)n元0-1向量為：n”); for(i=1;i<=n;i++) printf(“x%d ”,i); printf(“n”); //打印最優(yōu)n元0-1向量(x1,x2,x3……,xn) for(i=1;i<=n;i++) printf(“%-4d”,x[i]); printf(“n”);} 運行結果： 2009屆 電子信息科學與技術專業(yè) 數(shù)據(jù)結構課程設計 背包問題的求解 摘要 組合優(yōu)化問題的求解方法研究已經(jīng)成為了當前眾多科學關注的焦點，這不僅在于其內(nèi)在的復雜性有著重要的理論價值，同時也在于它們能在現(xiàn)實生活中廣泛的應用。背包問題是一個典型的組合優(yōu)化問題，本課程設計用遞歸算法求解背包問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。關鍵詞 背包問題； 遞歸算法； 1問題描述 1.1問題描述 背包問題：設有不同價值、不同重量的物品n件，求從這n件物品中選取一部分的方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。 1.2基本思想 （1）分別輸入n件物品的重量和價值。（2）采用遞歸尋找物品的方案。 （3）輸出最佳的裝填方案，包括選中的是哪幾種物品，總價值為多少。 2問題分析 背包問題的求解是一個很經(jīng)典的案例。對于它的分析與研究已經(jīng)到達了一定的深度，解決這個問題有很多很多的辦法。其中遞歸方法是比較簡化程序，也比較難理解的一個。 設n件物品的重量分別為w0,w1,?,wn-1,物品的價值分別為v0,v1,?,vn-1。采用遞歸尋找物品的選擇方案。設前面已經(jīng)有了多種選擇方案，并保留了其中最大的選擇方案于數(shù)組option[],設方案的的總價值存于變量maxv,當前正在考察新方案其物品選擇情況保存于數(shù)組cop[]，嘉定當前方案已經(jīng)考慮了前i-1件物品，現(xiàn)在正在考慮第i件物品；當前方案已經(jīng)包含的物品的質量之和為tw;至此，若其余物品都選擇可能的話，本方案能達到的總價值的期望值設為tv，算法引入tv是當一旦當前方案的總價值的期望值也小于前面方案的總價值maxv時，急需考察當前方案變成無意義的工作，應終止當前方案，立即去考察下一個方案。因為當方案的總價值不比maxv大時，該方案不會不會再被考察。這同時保證函數(shù)后找到的方案一定會比前面的方案更好。2009屆 電子信息科學與技術專業(yè) 數(shù)據(jù)結構課程設計 對于第i件物品的選擇有兩種可能： （1）物品i被選擇，這種可能性僅當包含它不會超過方案總重量的限制時才是可行的。選中后，繼續(xù)遞歸去考慮其余物品的選擇； （2）物品i不被選擇，這種可能性僅當不包物品i也有可能會找大價值更大的方案的情況。 就此，通過不斷地對從第一件開始的物品到第n件物品進行選擇或是不選擇，從而從各個方案的比較中選擇出最優(yōu)方案。 采用option[]和cop[]兩個數(shù)組，來輔助完成遞歸尋找物品的選擇方案。數(shù)組option[]起到一個“旗幟”作用，用來區(qū)別于未被選擇的物品，從而達到輸出被選擇的函數(shù)。而cop[]則像是一個中間變量，它在遞歸過程中不斷地發(fā)生變化，將有效的最終數(shù)據(jù)傳輸給數(shù)組option[]，起到一個橋梁作用。 3數(shù)據(jù)結構描述 背包問題結構體： struct{ int weight; int value; }a[N];4算法設計 4.1程序流程圖 2009屆 電子信息科學與技術專業(yè) 數(shù)據(jù)結構課程設計 圖4-1 程序流程圖 4.2算法設計 根據(jù)問題分析中的思想寫出遞歸算法如下： find（物品當前選擇已達到的重量和tw,本方案可能達到的總價值為tv）｛ /*考慮物品i包含在當前方案中的可能性*/ if（包含物品i是可接受的）｛ 將物品i包含在當前方案中； if(i 以當前方案作為臨時最佳方案保存； 恢復物品i不包含狀態(tài)； ｝ 2009屆 電子信息科學與技術專業(yè) 數(shù)據(jù)結構課程設計 /*考慮物品i不包含在當前方案中的可能性*/ if（不包含物品i僅是可考慮的） if(i 以當前方案作為臨時最佳方案保存； ｝ void find(int i,int tw,int tv) { int k;if(tw+a[i].weight<=limitw) /*物品i包含在當前方案的可能性*/ { cop[i]=1;if(i /*物品i不包含在當前方案的可能性*/ if(i opion[k]=cop[k];maxv=tv-a[i].value;} } 5詳細程序清單 詳細程序清單見附錄。 6程序運行結果 背包問題求解界面如圖6-1所示。 圖6-1 背包問題求解界面 程序調(diào)試成功。 在課程設計代碼調(diào)試過程中也出了不少差錯，比如頭文件很容易忽略，同學指出才發(fā)現(xiàn)；一些符號像“；”也很容易丟掉或是中英文格式不正確；甚至像0和 O這種小錯誤有時也會發(fā)生，在經(jīng)過調(diào)試和完善程序的過程中，這些錯誤已經(jīng)全部改正。在此過程中我們學到了不少調(diào)試的技巧，極大得豐富了編程的知識，這些在程序的優(yōu)化方面幫助很大。 7心得體會 通過此次課程設計的實踐，感觸較深。不僅使我們加深了對書本知識的理解，而且鍛煉了我們編寫程序、調(diào)試程序的能力。同時，此次課程設計也充分彌補了課堂教學中知識的缺陷。這次課程設計由于時間有限，對有些地方考慮的還不夠周到。 2009屆 電子信息科學與技術專業(yè) 數(shù)據(jù)結構課程設計 在本課題中，我們研究了如何用遞歸算法求解組合優(yōu)化問題中的背包問題，背包問題是一個典型的組合優(yōu)化問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。所以我們試著用所學的數(shù)據(jù)結構知識以及遞歸法來解決普通的背包問題。背包問題的遞歸思想確實有點難以理解，為了理解這個思想，我們確實花了很長時間，不過很高興最后經(jīng)過我們的討論掌握了這個思想。 參考文獻 [1] 徐孝凱.數(shù)據(jù)結構課程實驗.北京：清華大學出版社，2002:100-132 [2] 張乃笑.數(shù)據(jù)結構與算法.北京：電子工業(yè)出版，2000:3-5 [3] 嚴蔚敏.數(shù)據(jù)結構（C語言版）.北京： 清華大學出版社，2002:100-132 [4] 李春葆.數(shù)據(jù)結構（C語言篇）習題與解析（修訂版）.北京：清華大學出版，2000:45-66 Knapsack problem solving Li Shuai Zhu Zhili Kong Rongong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combinatorial optimization problem solving method has become the focus of attention of the scientific, it not only lies in its inherent complexity has the important theoretical value, but also that they can in real life widely.Knapsack problem is a typical combinatorial optimization problem, the course is designed to use recursion algorithm for solving knapsack problem was under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem;recursive algorithm 2009屆 電子信息科學與技術專業(yè) 數(shù)據(jù)結構課程設計 附錄：詳細程序清單 #include /*可實現(xiàn)最大總價值*/ int opion[N]，cop[N]; struct{ int weight; int value; }a[N];int n; void find(int i,int tw,int tv) { int k;if(tw+a[i].weight<=limitw) { cop[i]=1;if(i /*方案的選擇*/ /*當前方案的選擇*/ /*背包問題結構體*/ /*物品種數(shù)*/ /*物品i包含在當前方案的可能性*/ 7 2009屆 電子信息科學與技術專業(yè) 數(shù)據(jù)結構課程設計 if(tv-a[i].value>maxv) /*物品i不包含在當前方案的可能性*/ if(i 第%d種物品（重量，價值）：”,k+1);scanf(“%d,%d”,&w,&v);a[k].weight=w;a[k].value=v;totv+=v;} printf(“背包所能承受的總重量：”);scanf(“%d”,&limitw);maxv=0;for(k=0;k printf(“最佳裝填方案是：n”);for(k=0;k P07: 有依賴的背包問題 簡化的問題 這種背包問題的物品間存在某種“依賴”的關系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設沒有某個物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。算法 這個問題由NOIP2006金明的預算方案一題擴展而來。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的一個附件集合組成。按照背包問題的一般思路，僅考慮一個主件和它的附件集合?？墒?，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件后再選擇一個附件，選擇 主件后再選擇兩個附件??無法用狀態(tài)轉移方程來表示如此多的策略。（事實上，設有n個附件，則策略有2^n+1個，為指數(shù)級。） 考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應于P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應于這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉化并不能給出一個好的算法，因為物品組中的物品還是像原問題的策略一樣多。 再考慮P06中的一句話： 可以對每組中的物品應用P02中“一個簡單有效的優(yōu)化”。這提示我們，對于一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結果。所以，我們可以對主件i的“附件集合”先進行一次01背包，得到費用依次為0..V-c[i]所有這些值時相應的最大價值f'[0..V-c[i]]。那么這個主件及它的附件集合相當于V-c[i]+1個物品的物品 組，其中費用為c[i]+k的物品的價值為f'[k]+w[i]。也就是說原來指數(shù)級的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉化為 V-c[i]+1個物品的物品組，就可以直接應用P06的算法解決問題了。 較一般的問題 更一般的問題是：依賴關系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多只依賴于一個物品（只有一個主件）且不出現(xiàn)循環(huán)依賴。 解決這個問題仍然可以用將每個主件及其附件集合轉化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個附件都看作一個一般的01背 包中的物品了。若這個附件也有附件集合，則它必定要被先轉化為物品組，然后用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。 事實上，這是一種樹形DP，其特點是每個父節(jié)點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性。這已經(jīng)觸及到了“泛化物品”的思想?？赐關08后，你會發(fā)現(xiàn)這個“依賴關系樹”每一個子樹都等價于一件泛化物品，求某節(jié)點為根的子樹對應的泛化物品相當于求其所有兒子的對應的泛化物品之和。 小結 NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未得。后來我通過思考發(fā)現(xiàn)通過引入“物品組” 和“依賴”的概念可以加深對這題的理解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件，每個主件最多 有兩個附件，可以發(fā)現(xiàn)一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問題的某種本質。 我想說：失敗不是什么丟人的事情，從失敗中全無收獲才是。第四篇：數(shù)據(jù)結構課程設計 背包問題的求解
第五篇：P07-有依賴的背包問題
點擊咨詢 