编辑代码

#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
 

int knapsack(int n, int w[], int v[], int C) {
  // dp[j] 表示容量为j的背包的最大价值
  int dp[C+1];
  // 初始化边界条件
  for (int j = 0; j <= C; j++) {
    dp[j] = 0; // 没有物品可选，价值为0
  }
  // 状态转移方程
  for (int i = 1; i <= n; i++) {
    for (int j = C; j >= w[i-1]; j--) { // 倒序遍历，避免覆盖之前的状态
      // 在放入和不放入第i个物品中选择最大价值
      dp[j] = max(dp[j], dp[j-w[i-1]] + v[i-1]);
    }
  }
  // 返回最终结果
  return dp[C];
}
 
int main() {
  // 测试数据
  int num = 3;
  int weight[] = {1,3,4};    //测试用例
  int value[] = {1500,2000,3000};
  int capacity = 4;
  // 调用函数
  int ans = knapsack(num,weight,value,capacity);
  // 输出结果
  printf("The maximum value is %d\n", ans);
  return 0;
}