第一篇：2背包问题九讲之完全背包问题
P02: 完全背包问题
题目
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件„„等很多种。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样： f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
这跟01背包问题一样有O(VN)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态f[i][v]的时间是O(v/c[i])，总的复杂度可以认为是O(V*Σ(V/c[i]))，是比较大的。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。
一个简单有效的优化
完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。
这个优化可以简单的O(N^2)地实现，一般都可以承受。另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化。这个不太重要的过程就不给出伪代码了，希望你能独立思考写出伪代码或程序。
转化为01背包问题求解
既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c[i]件，于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
更高效的转化方法是：把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足c[i]*2^k<=V。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品，是一个很大的改进。但我们有更优的O(VN)的算法。
O(VN)的算法
这个算法使用一维数组，先看伪代码：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
你会发现，这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。
值得一提的是，上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
这个算法也可以以另外的思路得出。例如，将基本思路中求解f[i][v-c[i]]的状态转移方程显式地写出来，代入原方程中，会发现该
方程可以等价地变形成这种形式：
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
将这个方程用一维数组实现，便得到了上面的伪代码。
最后抽象出处理一件完全背包类物品的过程伪代码：
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
总结
完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。
第二篇：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;}
第三篇：P07-有依赖的背包问题
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的那道背包问题我做得很失败，写了上百行的代码，却一分未得。后来我通过思考发现通过引入“物品组” 和“依赖”的概念可以加深对这题的理解，还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多 有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。
我想说：失败不是什么丢人的事情，从失败中全无收获才是。
第四篇：数据结构课程设计 背包问题的求解
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 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”);} 运行结果：第五篇：0-1背包问题c语言程序
![下载2背包问题九讲之完全背包问题[优秀范文五篇]word格式文档](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
点击咨询 