#include <stdio.h>
#include <stdlib.h>
typedef struct Goods{
    int weight; 
    int value;  
} Goods; 
int getSurplusValue(Goods *goodArr, int n, int i) {
    int surplusValue = 0;
    for (int j = i; j < n; j++) 
        surplusValue += goodArr[j].value; 
    return surplusValue;
} 
int dfs(Goods *goodArr, int n, int totalWeight, int *way, int *bestWay, 
                    int i, int currWeight, int currValue, int bestValue) {
    if (i >= n) {
        bestValue = currValue;
        for (int k = 0; k < n; k++)  
            bestWay[k] = way[k]; 
        return bestValue;
    } 
    // 搜索左子树
    if (currWeight + goodArr[i].weight <= totalWeight) {
        currWeight += goodArr[i].weight;
        currValue += goodArr[i].value;
        way[i] = 1;
        bestValue = dfs(goodArr, n, totalWeight, way, bestWay, i + 1, 
                                        currWeight, currValue, bestValue);
        currWeight -= goodArr[i].weight;
        currValue -= goodArr[i].value;
        way[i] = 0;
    } 
    // 搜索右子树
    if (currValue + getSurplusValue(goodArr, n, i + 1) >= bestValue) {
        bestValue = dfs(goodArr, n, totalWeight, way, bestWay, i + 1, 
                                        currWeight, currValue, bestValue);
    } 
    return bestValue;
} 
int main() {
    Goods goodArr[] = { {1, 5}, {2, 6}, {3, 7}, {4, 8}  };
    int totalWeight = 8;
    int n = sizeof(goodArr) / sizeof(goodArr[0]);  
    int way[n], bestWay[n];
    int bestValue = 0;  
    bestValue = dfs(goodArr, n, totalWeight, way, bestWay, 0, 0, 0, bestValue); 
    printf("最大价值可为: %d\n", bestValue);
    printf("各包的取舍状态为：\n");
    for (int i = 0; i < n; i++) 
        printf("重量为: %d 的: %d\n", goodArr[i].weight, bestWay[i]); 
    return 0;
}