回溯法解决0-1背包问题（王晓东算法例题）
发布时间
阅读量：
阅读量
假设有n类物品及一个背包。其中，物品i的重量为wi，对应的价值为vi，而背包的最大承载能力为C。问题在于如何挑选合适的物品装入背包，以实现所装载物品总价值的最大化？
整个求解过程可视为一棵二叉树的结构，左分支表示不选择当前物品（标记为0），右分支表示选择该物品（标记为1），随后通过深度优先搜索的方式进行遍历，在回溯过程中对状态进行相应的调整。
需要指出的是，此处应当包含两种剪枝策略，但目前仅展示了一种。
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int n,TotCap,bestval;//物品的个数，背包的容量，最大价值
const int N=1000;
int val[N],w[N],x[N],bestx[N];//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况
void dfs(int i,int cv,int cw)
{ //cw当前包内物品重量，cv当前包内物品价值
if(i>n)//结束
{
if(cv>bestval)
{
全部评论 (0)
还没有任何评论哟~