经典问题：
给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？？
分析
1、如上图碰到一组数据，有两种可能:选或者不选，在树种分别由1，0表示。
2、使用递归，在遍历完n个数的时候，判断最终的数是否比最佳价值大，如果比最佳价值大，就把值赋给bestv。
代码：
#include
int c=30; //背包容量 int n=3; //对象数目 int w[]={20,15,15}; //对象重量数组 int v[]={40,25,25}; //对象收益数组 int cw; //当前背包重量 int cv; //当前背包价值 int bestv;//迄今最大的收益 int X[n]; //记录在树中的移动路径,为1的时候表示选择该组数据，为0的表示不选择该组数据 void getBest(int i) { if(i>=n)//递归结束的判定条件 { if(cv>bestv) bestv=cv; return; } if(cw+w[i]<=c)//进入该节点的右孩子（值为1的孩子） { X[i]=1; cw+=w[i]; cv+=v[i]; getBest(i+1); cw-=w[i];//此处回溯 cv-=v[i]; } X[i]=0;//进入该节点的右孩子（值为0的孩子） getBest(i+1); } int main() { getBest(0); printf("%d",bestv); return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/178598.html原文链接：https://javaforall.net
