Statement

เพื่อความเข้าใจที่ตรงกัน ขอทบทวนปัญหาและตั้งชื่อตัวแปรต่าง ๆ ดังนี้ มีส่วนผสมสำหรับทำเปอร์เก็ต $n$ ชนิด $(1 \leq n \leq 10)$ แต่ละชนิดมีค่าความเปรี้ยว $S$ (sourness) และความขม $B$ (bitterness) สำหรับความเปรี้ยวของส่วนผสมชนิดที่ $i$ จะเขียนแทนด้วย $s[i]$ และค่าความขมของส่วนผสมชนิดที่ $i$ เขียนแทนด้วย $b[i]$ โดย $0 \leq i < n$

จงเลือกส่วนผสมอย่างน้อย $1$ ชนิดอย่างไรก็ได้ ให้ค่าความต่างระหว่างผลคูณของค่า $s[i]$ ที่เลือก กับผลบวกของค่า $b[i]$ ที่เลือก มีค่าน้อยที่สุดเท่าที่เป็นไปได้

Solution

เนื่องจากจำนวนของส่วนผสมมีจำนวนน้อย $(n \leq 10)$ ดังนั้นสามารถทดลองเลือกส่วนผสมของทุก ๆ ซับเซตและหาค่าผลต่างระหว่างผลคูณของค่าความเปรี้ยวและผลบวกของค่าความขมที่น้อยที่สุดเท่าที่เป็นไปได้

กำหนด 3 ตัวแปรสำหรับการแก้ปัญหาด้วยฟังก์ชันเรียกตัวเอง (recursive function) ดังนี้

• เลขดัชนี $i$ (index) ของส่วนผสมชนิดต่อไปซึ่งเราจะใช้เลขนี้เป็นตัวตัดสินใจว่าจะเลือกหรือไม่เลือกส่วนผสมชนิดที่ $i$
• ค่าผลคูณความเปรี้ยวรวม (sourness) ที่เคยเลือกมา
• ค่าผลรวมความขม (bitterness) ที่เคยเลือกมา

ในการเรียก recursive function แต่ละครั้ง เราจะสร้างการตัดสินใจอย่างใดอย่างหนึ่งใน $2$ ทางเลือกดังนี้

• ทางเลือกที่เราจะไม่หยิบส่วนผสมชนิดที่ $i$ และไปพิจารณาการตัดสินลักษณะนี้กับส่วนผสมชนิดต่อไป
• อีกทางเลือกคือเราจะทำการหยิบส่วนผสมชนิดที่ $i$ (ซึ่งเมื่อหยิบมาแล้ว เราต้องเปลี่ยนแปลงค่าความเปรี้ยวรวมกับค่าความขมรวมด้วย) จากนั้นก็ไปพิจารณาการตัดสินใจลักษณะนี้กับส่วนผสมชนิดต่อไป

Code

#include <stdio.h>

#define MAXN 10

int n, s[MAXN], b[MAXN], best = 1000000000;

int diff(int x, int y) { return x < y ? y - x : x - y; }

void recur(int i, int sourness, int bitterness) {
  if (i == n) {
    if (bitterness > 0 && diff(sourness, bitterness) < best)
      best = diff(sourness, bitterness);
  } else {
    recur(i + 1, sourness, bitterness);               // กรณีไม่เลือกส่วนผสมชนิดที่ i
    recur(i + 1, sourness * s[i], bitterness + b[i]); // กรณีที่เลือกส่วนผสมชนิดที่ i
  }
}

int main(void) {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &s[i], &b[i]);

  recur(0, 1, 0);

  printf("%d\n", best);
  return 0;
}