编辑代码

#include<stdio.h>

struct item{
    char name[50];
    int weight;
    int value;
};

int max(int a,int b){
    if(a >= b){
        return a;
    }else{
        return b;
    }
}

int KnapSack(int length,struct item product[], int capacity){
    int V[length + 1][capacity + 1];
    for(int i = 0; i <= length; i++){
        for(int j = 0; j <= capacity; j++){
            V[i][j] = 0;
        }
    }

    for(int i = 1; i <= length; i++){
        for(int j = 1; j <= capacity; j++){
            if(j < product[i - 1].weight){
				V[i][j] = V[i - 1][j];
			}else{
                V[i][j] = max(V[i - 1][j], V[i - 1][j - product[i - 1].weight] + product[i - 1].value);
			}
		}
	}

        int select[length];
        int j = capacity;
        for(int i = length; i >= 1; i--){
            if(V[i][j] > V[i - 1][j]){
				select[i] = 1;
				j = j - product[i - 1].weight;
            }else{
                select[i] = 0;
            }
        }
        printf("选中的景点为:\n");
        for(int i = 0; i <= length; i++){
            if(select[i + 1] == 1){
                printf("%s\n",product[i].name);
            }
        }
        printf("\n");
    return V[length][capacity]; 
}

int main(){
    struct item product[5] = {{"威斯敏斯特教堂", 5, 7}, {"环球剧场", 5, 6}, {"英国国家美术馆", 10, 9}, {"大英博物馆", 20, 9}, {"圣保罗大教堂", 5, 8}};
    int length = sizeof(product) / sizeof(product[0]);
    int capacity = 20;

    int sum = KnapSack(length, product, capacity);

    printf("最大景点评分为:\n");
    printf("%d\n",sum);
   
    return 0;
}