编辑代码

#include <stdio.h>
struct item{
    char name[20];
    int weight;
    int value;
};

int dynamicBackpack(struct item product[], int length, int packCapacity){
    int maxValue[length][packCapacity];
    int max =  0;
    for(int i = 0; i < length; i++){
        for(int j = 0; j < packCapacity; j++){
            if(i == 0){
                maxValue[i][j] = product[i].value;
            }else if(j + 1 >= product[i].weight){
                if(maxValue[i - 1][j] + product[i].value > product[i].value && j + 1 >= product[i].weight + product[i - 1].weight){
                    maxValue[i][j] = maxValue[i - 1][j] + product[i].value;
                }else if(maxValue[i - 1][j] > product[i].value){
                    maxValue[i][j] = maxValue[i - 1][j];
                }else{
                    maxValue[i][j] = product[i].value;
                }
            }else if(j + 1 < product[i].weight){
                maxValue[i][j] = maxValue[i - 1][j];
            }
        }
    }

    for(int i = 0; i < length; i++){
        for(int j = 0; j < packCapacity; j++){
            if(maxValue[i][j] > max){
                max = maxValue[i][j];
            }
        }
    }

    return max;
}

int main () {
    struct item product[3] = {{"guitar", 1, 1500}, {"laptop", 3, 2000}, {"sound", 4, 3000}};
    int length = sizeof(product) / sizeof(product[0]);
    int packCapacity = 4;
    printf("在背包容量为4磅时，最多可拿价值为%d美元的商品。",dynamicBackpack(product, length, packCapacity));
    return 0;
}