ITSA 54 - [Problem 2] 量販店活動 - 參考答案

Difficulty: Eazy
Ref: ITSA 54 - [Problem 2] 量販店活動

/*******************************************************/
/* ITSA 54 - [Problem 2] 量販店活動                     */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/15                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main() {
 int m;
 scanf("%d", &m);
 while (m--) {
  int i, j, goods[10][2], mx_weight, n, bag[101] = { 0 };
  scanf("%d%d", &mx_weight, &n);
  for (i = 0; i < n; i++){
   scanf("%d%d", goods[i], goods[i] + 1);
   while (getchar() != '\n');
  }
  for (i = 0; i < n; i++)
   for (j = goods[i][0]; j <= mx_weight; j++) {
    int term = bag[j - goods[i][0]] + goods[i][1];
    if (term > bag[j])
     bag[j] = term;
   }
  printf("Total: %d\n", bag[mx_weight]);
 }
}

Debug： I/O
簡單的背包問題，使用動態規劃以減少時間複雜度，才能在限制時間內算出答案。
可以參考背包問題詳細說明：背包問題（Knapsack Problem）

2
15
5
6 6000 watch
4 4500 beverage
5 5500 fruit
3 2500 bread
2 2100 coke
99
9
3 2500 bread
7 6500 bagel
4 4500 yogurt
5 5500 watch
10 11500 beverage
8 8500 fruit
9 1100 jam
2 2200 coke
6 6000 juice

Total: 16600
Total: 113500