编辑代码

#include<stdio.h>  
#include<iostream>  
#define n 5//多少物品  
int w[n] = {6,5,4,2,1};//重量  
int v[n] = {5,3,5,3,2};//价值  
int c = 10;//背包限重  
int flag[n],best[n];  
int temp;  
int max;  
int maxvalue;//最大价值  
int rest;  
void nfs(int m)  
{  
    int i;  
    if(m == n){  
        if(temp > max){  
            max = temp;  
            for(i = 0;i < n;i ++){  
                best[i] = flag[i];  
            }  
        }  
        return;  
    }  
    if(temp + rest > max){  
        if(temp + w[m] <= c){  
            temp += w[m];  
            flag[m] = 1;  
            rest -= w[m];  
            nfs(m + 1);  
            rest += w[m];  
            temp -= w[m];  
        }  
        rest -= w[m];  
        flag[m] = 0;  
        nfs(m + 1);  
        rest += w[m];  
    }  

}  
int main()  
{  
    int i;  
    temp = 0;  
    rest = 0;  
    for(i = 0;i < n;i ++)  
        rest += w[i];  
    nfs(0);  

    for(i = 0;i < n;i ++){  
        if(best[i] == 1){  
            std::cout<<"选择物品第"<< i+1 <<"个 重量为"<<w[i]<<" ";  
            maxvalue += v[i];  
        }  
    }  
    std::cout<<"最大价值为："<<max<<std::endl;  
    std::cout<<std::endl;  
    return 0;  

}