题解 | #01背包#

有些问题绕了几个圈终于想通了。。自己就是个弟弟。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
  //  dp_value[i] 表示体积为i所能装的最大价值数
  //  dp_weight[i] 表示体积为i时所能装的最大价值数（初始化值不同）
  int dp_value[1001] = {0};
  int dp_weight[1001] = {0};
  memset(dp_weight, -0x3f, sizeof(dp_weight));
  dp_weight[0] = 0;
  int value[1001] = {0};
  int weight[1001] = {0};
  int count = 0, size = 0, res = 0;
  
  scanf("%d %d", &count, &size);
  
  for (int i = 0; i < count; ++i) {
    scanf("%d %d", &weight[i], &value[i]);
  }
  
  //  第二层循环反向是为了每个物体作为一层，从大到小不会覆盖上一层的数据
  for (int i = 0; i < count; ++i) {
    for (int j = size; j >= weight[i]; --j) {
      //  求最大价值数
      dp_value[j] = dp_value[j - weight[i]] + value[i] > dp_value[j] ? dp_value[j - weight[i]] + value[i] : dp_value[j];
      //  必须从零的状态转移，不然其价值都是为负数（初始化负数足够小），零状态即代表背包塞满了
      dp_weight[j] = dp_weight[j - weight[i]] + value[i] > dp_weight[j] ? dp_weight[j - weight[i]] + value[i] : dp_weight[j];
    }
  }
  
  printf("%d\n", dp_value[size]);
  
  if (dp_weight[size] < 0) {
    printf("0\n");
  } else {
    printf("%d\n", dp_weight[size]);
  }
  
  return 0;
}