编辑代码

#include <stdio.h>  
// 物品结构体  
typedef struct {  
    int weight;  
    int value;  
} Item;  

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

// 动态规划函数  
int knapsack(Item items[], int n, int W) {  
    int i, w;  
    int K[n + 1][W + 1];  // 用于保存子问题的解  
  
    // 初始化DP表格  
    for (i = 0; i <= n; i++) {  
        for (w = 0; w <= W; w++) {  
            if (i == 0 || w == 0) {  
                K[i][w] = 0;  
            } else if (items[i - 1].weight <= w) {  
                K[i][w] = max(items[i - 1].value + K[i - 1][w - items[i - 1].weight], K[i - 1][w]);  
            } else {  
                K[i][w] = K[i - 1][w];  
            }  
        }  
    }  
    return K[n][W];  // 返回最大价值  
}  
  
int main() {  
    // 物品数组，每个元素表示一个物品的重量和价值
    Item items[] = {{2, 3}, {3, 4}, {4, 5}, {5, 6}};
    // 输出最大价值
    printf("最大价值为: %d\n", knapsack(items, sizeof(items) / sizeof(Item), 5));    

    // 物品数组，每个元素表示一个物品的重量和价值  
    Item items2[] = {{1, 3}, {2, 4}, {3, 5}, {4, 6}}; 
    // 输出最大价值  
    printf("最大价值为: %d\n", knapsack(items2, sizeof(items) / sizeof(Item), 5));  

    // 物品数组，每个元素表示一个物品的重量和价值 
    Item items3[] = {{5, 3}, {6, 4}, {7, 5}, {8, 6}};  
    // 输出最大价值 
    printf("最大价值为: %d\n", knapsack(items3, sizeof(items) / sizeof(Item), 5));  
    return 0;  
}