对于0-1 背包问题可以用动态规划算法解决,这里先不说这种方法。
只介绍回溯法,0-1背包问题的回溯法解决的解空间是子集树。
下面给出最简洁的代码,比较方便理解呢
#include <iostream>
#include<stdio.h>
using namespace std;
int n,c,bestp;//物品的个数,背包的容量,最大价值
int p[10000], //物品的价值
w[10000], //物品的重量
x[10000], //x[i]暂存物品的选中情况
bestx[10000]; //物品的选中情况
void Backtrack(int i,int cp,int cw)
{
//cw当前包内物品重量,cp当前包内物品价值
int j;
if(i>n)//回溯结束
{
if(cp>bestp)
{
bestp=cp;
for(i=0; i<=n; i++) bestx[i]=x[i];
}
}
else
for(j=0; j<=1; j++)
{
x[i]=j;
if(cw+x[i]*w[i]<=c)
{
cw+=w[i]*x[i];
cp+=p[i]*x[i];
Backtrack(i+1,cp,cw);
cw-=w[i]