题解 | #装箱问题#

突然不理解这道题了。。写错写不出来。。

#include <stdio.h>

int main(int argc, char *argv[]) {
  //  dp[i] 表示i容量时所能装的最大物品体积
  int dp[20001] = {0};
  int object[30] = {0};
  
  int size, count;
  scanf("%d", &size);
  scanf("%d", &count);
  
  for (int i = 0; i < count; ++i) {
    scanf("%d", &object[i]);
  }
  
//   for (int i = 1; i <= size; ++i) {
//     for (int j = 0; j < count; ++j) {
//       if (object[j] <= i) {
//         dp[i] = dp[i - object[j]] + object[j] > dp[i] ? dp[i - object[j]] + object[j] : dp[i];
//       }
//     }
//   }
  
  for (int i = 0; i < count; ++i) {
    for (int j = size; j >= object[i]; --j) {
      dp[j] = dp[j - object[i]] + object[i] > dp[j] ? dp[j - object[i]] + object[i] : dp[j];
    }
  }
  
  printf("%d\n", size - dp[size]);
  
  return 0;
}