第一篇：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，设数组dp[1],dp[2],…,dp[mk-1],dp[mk]（注意，dp不包含0包含mk）表示当包内放了1,2,…,mk-1,mk质量的东西时能达到的最大价值。
2.问题：
如何安排放置在背包里的物品使得背包内物品总价值能达到最大？（假设每种类型物品个数是无限的）
3.算法：
第一步：将n种物品按照质量从小到大排序，相应的价值也要跟着质量数组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] };
}
最终执行完毕后，dp[mk]值即为包内放置mk质量的东西时能达到的最大价值的值！
4.特例：
当题目只给你质量而没有价值时，不放设价值和质量取相同值，转化为特殊的0-1背包问题，如上解问题。当题目只给你价值而没有质量时也不妨设质量和价值取相同值，同样用上述方法解决问题。
5.思路： 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。可以压缩空间，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;/*初始化数组*/
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(“请输入背包的承重量,物品的总个数：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件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则多出来的空间里能放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.最优值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]);//最后的值即为最优值，返回主函数 }
2.求最优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]);//最后的值即为最优值，返回主函数 }
//求最优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(“输入背包容量和货物个数：”);
scanf(“%d%d”,&m,&n);p=(int *)calloc(n,sizeof(int));//分配n*sizeof(int)的内存大小，存取n个物品的价格
w=(int *)calloc(n,sizeof(int));//分配n*sizeof(int)的内存大小，存取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++)//打印执行动态规划每步的值 for(int j=0;j<=m;j++) { printf(“%3d ”,c[i][j]); if(j==m) printf(“n”); } getbest(m,n,w,p); printf(“最优n元0-1向量为：n”); for(i=1;i<=n;i++) printf(“x%d ”,i); printf(“n”); //打印最优n元0-1向量(x1,x2,x3……,xn) for(i=1;i<=n;i++) printf(“%-4d”,x[i]); printf(“n”);} 运行结果： 2009届 电子信息科学与技术专业 数据结构课程设计 背包问题的求解 摘要 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。关键词 背包问题； 递归算法； 1问题描述 1.1问题描述 背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。 1.2基本思想 （1）分别输入n件物品的重量和价值。（2）采用递归寻找物品的方案。 （3）输出最佳的装填方案，包括选中的是哪几种物品，总价值为多少。 2问题分析 背包问题的求解是一个很经典的案例。对于它的分析与研究已经到达了一定的深度，解决这个问题有很多很多的办法。其中递归方法是比较简化程序，也比较难理解的一个。 设n件物品的重量分别为w0,w1,„,wn-1,物品的价值分别为v0,v1,„,vn-1。采用递归寻找物品的选择方案。设前面已经有了多种选择方案，并保留了其中最大的选择方案于数组option[],设方案的的总价值存于变量maxv,当前正在考察新方案其物品选择情况保存于数组cop[]，嘉定当前方案已经考虑了前i-1件物品，现在正在考虑第i件物品；当前方案已经包含的物品的质量之和为tw;至此，若其余物品都选择可能的话，本方案能达到的总价值的期望值设为tv，算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，急需考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会不会再被考察。这同时保证函数后找到的方案一定会比前面的方案更好。2009届 电子信息科学与技术专业 数据结构课程设计 对于第i件物品的选择有两种可能： （1）物品i被选择，这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后，继续递归去考虑其余物品的选择； （2）物品i不被选择，这种可能性仅当不包物品i也有可能会找大价值更大的方案的情况。 就此，通过不断地对从第一件开始的物品到第n件物品进行选择或是不选择，从而从各个方案的比较中选择出最优方案。 采用option[]和cop[]两个数组，来辅助完成递归寻找物品的选择方案。数组option[]起到一个“旗帜”作用，用来区别于未被选择的物品，从而达到输出被选择的函数。而cop[]则像是一个中间变量，它在递归过程中不断地发生变化，将有效的最终数据传输给数组option[]，起到一个桥梁作用。 3数据结构描述 背包问题结构体： struct{ int weight; int value; }a[N];4算法设计 4.1程序流程图 2009届 电子信息科学与技术专业 数据结构课程设计 图4-1 程序流程图 4.2算法设计 根据问题分析中的思想写出递归算法如下： find（物品当前选择已达到的重量和tw,本方案可能达到的总价值为tv）｛ /*考虑物品i包含在当前方案中的可能性*/ if（包含物品i是可接受的）｛ 将物品i包含在当前方案中； if(i 以当前方案作为临时最佳方案保存； 恢复物品i不包含状态； ｝ 2009届 电子信息科学与技术专业 数据结构课程设计 /*考虑物品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 背包问题求解界面 程序调试成功。 在课程设计代码调试过程中也出了不少差错，比如头文件很容易忽略，同学指出才发现；一些符号像“；”也很容易丢掉或是中英文格式不正确；甚至像0和 O这种小错误有时也会发生，在经过调试和完善程序的过程中，这些错误已经全部改正。在此过程中我们学到了不少调试的技巧，极大得丰富了编程的知识，这些在程序的优化方面帮助很大。 7心得体会 通过此次课程设计的实践，感触较深。不仅使我们加深了对书本知识的理解，而且锻炼了我们编写程序、调试程序的能力。同时，此次课程设计也充分弥补了课堂教学中知识的缺陷。这次课程设计由于时间有限，对有些地方考虑的还不够周到。 2009届 电子信息科学与技术专业 数据结构课程设计 在本课题中，我们研究了如何用递归算法求解组合优化问题中的背包问题，背包问题是一个典型的组合优化问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。所以我们试着用所学的数据结构知识以及递归法来解决普通的背包问题。背包问题的递归思想确实有点难以理解，为了理解这个思想，我们确实花了很长时间，不过很高兴最后经过我们的讨论掌握了这个思想。 参考文献 [1] 徐孝凯.数据结构课程实验.北京：清华大学出版社，2002:100-132 [2] 张乃笑.数据结构与算法.北京：电子工业出版，2000:3-5 [3] 严蔚敏.数据结构（C语言版）.北京： 清华大学出版社，2002:100-132 [4] 李春葆.数据结构（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届 电子信息科学与技术专业 数据结构课程设计 附录：详细程序清单 #include /*可实现最大总价值*/ 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 /*方案的选择*/ /*当前方案的选择*/ /*背包问题结构体*/ /*物品种数*/ /*物品i包含在当前方案的可能性*/ 7 2009届 电子信息科学与技术专业 数据结构课程设计 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金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择 主件后再选择两个附件„„无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。） 考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于P06中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。 再考虑P06中的一句话： 可以对每组中的物品应用P02中“一个简单有效的优化”。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0..V-c[i]所有这些值时相应的最大价值f'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品 组，其中费用为c[i]+k的物品的价值为f'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为 V-c[i]+1个物品的物品组，就可以直接应用P06的算法解决问题了。 较一般的问题 更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。 解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背 包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。 事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。 小结 NOIP2006的那道背包问题我做得很失败，写了上百行的代码，却一分未得。后来我通过思考发现通过引入“物品组” 和“依赖”的概念可以加深对这题的理解，还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多 有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。 我想说：失败不是什么丢人的事情，从失败中全无收获才是。第四篇：数据结构课程设计 背包问题的求解
第五篇：P07-有依赖的背包问题
点击咨询 