编辑代码

#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]<<"kg"<<"，";
            maxvalue += v[i];
        }
    }
    std::cout<<"最大价值为："<<max<<std::endl;
    std::cout<<std::endl;
    return 0;
}