#include <stdio.h>
int cv;//当前价值
int cw;//当前重量
int bestv;//当前最优价值
int bestx[6];//当前最优解
int c=10;//背包容量
int n=5;//物品个数
//计算当前结点处的上界
float Bound(int i,int *v,int *w) {
    int left=c-cw;     //剩余容量
    float b=(float)cv;
    while (i <=n&&w[i] <=left) {
        left-=w[i];
        b+=v[i];
        i++;
    }
//装满背包
    if (i <=n)b+=(float)(v[i]/w[i])*left;
    return b;
}
void Backtrack(int i,int *v,int *w,int *x) {
    if (i> n) {
        for (int j=1;j <=n;j++)
            bestx[j]=x[j];
        bestv=cv;
    } else {
        for (int t=0;t <=1;t++) {
            x[i]=t;
            if (cw+w[i] <=c&&Bound(i+1,v,w)> bestv) {
                if (x[i]==1) {
                    cw+=w[i];
                    cv+=v[i];
                }
                Backtrack(i+1,v,w,x);
                if (x[i]==1) {
                    cw-=w[t];
                    cv-=v[t];
                }
            }
        }
    }

    if (Bound(i+1,v,w)> (float)bestv) { //搜索右子树
        x[i]=0;
        Backtrack(i+1,v,w,x);
    }
}

void main() {
    int w[6]={0,2,2,6,5,4},v[6]={0,6,3,5,4,6};//0号单元不用
    int x[6];//当前解
    cv=0;
    cw=0;
    bestv=0;
    Backtrack(1,v,w,x);
    printf("选择的物品:");
    for (int i=1;i <=5;i++)
        if (bestx[i]==1)printf("% d",i);
    printf("\n");
    printf("最大价值和为:%d\n",bestv);
    getchar();
}