WeChall - The Travelling Customer

Posted on In Views: Disqus:

The Travelling Customer (Coding, Training) by gizmore XKCD 287 风格 bounded knapsack——5 轮，每轮 3 秒限时

Challenge

页面给一个 pricelist，要求选出指定数量的商品，使总价等于目标值，且每类商品不超过 stock。需要连续解 5 轮，每轮 3 秒。

1
2
3
Endpoint: /en/challenge/training/programming/knapsaak/
  problem.php     → 返回新问题
  answer.php?answer=<answer>   → 提交答案（GET 方式）

题目参数（problem.php 返回的纯文本格式）：

1
2
3
4
5
6
7
8
Items=50
Sum=5001
Stock=2
Level=1
Pizza=713
Chips=590
Eggs=523
...

Solution

这是 bounded knapsack（精确总价 + 精确件数 + 库存限制）。DFS + memo 即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import requests

BASE = 'https://www.wechall.net/en/challenge/training/programming/knapsaak'
COOKIES = {'WC': '...'}

def parse_problem(text):
    items = []
    meta = {}
    for line in text.strip().split('\n'):
        if '=' not in line: continue
        k, v = line.split('=', 1)
        k, v = k.strip(), v.strip()
        if k in ('Items', 'Sum', 'Stock', 'Level'):
            meta[k] = int(v)
        else:
            items.append((k, int(v)))   # (name, price)
    return items, meta['Items'], meta['Sum'], meta['Stock']

def solve(items, need_count, need_sum, stock):
    n = len(items)
    prices = [p for _, p in items]
    names = [n for n, _ in items]
    # 按价格降序排列（剪枝效果更好）
    order = sorted(range(n), key=lambda i: -prices[i])
    sp = [prices[i] for i in order]

    memo = {}
    def dfs(idx, ri, rs):
        if ri == 0 and rs == 0:
            return [0] * (n - idx)
        if idx == n or ri < 0 or rs < 0:
            return None
        key = (idx, ri, rs)
        if key in memo:
            return memo[key]
        # 剪枝：剩余件数超出库存限制
        if ri > stock * (n - idx):
            memo[key] = None; return None
        # 剪枝：剩余金额超出价格范围
        min_p, max_p = min(sp[idx:]), max(sp[idx:])
        if rs < ri * min_p or rs > ri * max_p:
            memo[key] = None; return None

        p = sp[idx]
        for qty in range(min(stock, ri, rs // p) + 1):
            sub = dfs(idx + 1, ri - qty, rs - qty * p)
            if sub is not None:
                memo[key] = [qty] + sub
                return memo[key]
        memo[key] = None
        return None

    qs = dfs(0, need_count, need_sum)
    if qs is None: return None
    # 按原始顺序还原
    quants = [0] * n
    for i, orig_idx in enumerate(order):
        quants[orig_idx] = qs[i]
    # 拼接答案：qtyName...
    return ''.join(str(quants[i]) + names[i]
                   for i in range(n) if quants[i] > 0)

s = requests.Session()
s.cookies.update(COOKIES)

for round_num in range(5):
    resp = s.get(f'{BASE}/problem.php')
    items, cnt, target, stock = parse_problem(resp.text)
    answer = solve(items, cnt, target, stock)
    resp2 = s.get(f'{BASE}/answer.php', params={'answer': answer})
    print(f'Round {round_num+1}: {resp2.text.strip()}')

Key Points:

  • GET 请求：抓题和提交都用 GET（不是 POST），不需要 CSRF token
  • Cookie 复用：用 requests.Session() 保持同一会话，5 轮连续
  • Answer 格式：数量直接拼接商品名，无分隔符。例如 2Pizza3Chips1Eggs
  • 3 秒限时：每轮从抓题到提交必须在 3 秒内完成，所以必须自动化
  • 剪枝：价格排序 + 剩余范围检查，避免 DFS 爆炸
  • session-bound：每轮题目随机，答案不固定，无法直接复用