結果

問題 No.2492 Knapsack Problem?
コンテスト
ユーザー はにはに
提出日時 2025-01-09 01:56:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,448 bytes
コンパイル時間 285 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 76,200 KB
最終ジャッジ日時 2025-01-09 01:56:50
合計ジャッジ時間 1,817 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 2 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Knapsack:
    def __init__(self, VW):
        self.VW = sorted(VW, key=lambda vw: vw[0] / vw[1], reverse=True)
        self.n = len(VW)
        self.memo = {}  # メモ化用の辞書を初期化
        
        self.cumulative_values = [0] * (self.n + 1)
        self.cumulative_weights = [0] * (self.n + 1)
        
        for i in range(self.n):
            v, w = self.VW[i]
            self.cumulative_values[i+1] = self.cumulative_values[i] + v
            self.cumulative_weights[i+1] = self.cumulative_weights[i] + w


    def solve(self, capacity, ok=0):
        self.ok = ok
        self.capacity = capacity
        return self._dfs(0, 0, 0)

    def _dfs(self, i, v_now, w_now):
        if (i, v_now, w_now) in self.memo:
            return self.memo[(i, v_now, w_now)]
        if i == self.n:
            self.ok = max(self.ok, v_now)
            self.memo[(i, v_now, w_now)] = v_now
            return v_now

        ng, f = self._solve_relaxation(i, self.capacity-w_now)
        ng += v_now
        if f:
           self.ok = max(self.ok, ng)
           self.memo[(i,v_now,w_now)] = ng
           return ng
        if ng < self.ok:
           self.memo[(i,v_now,w_now)] = -float('inf')
           return -float('inf')

        res = -float("inf")
        v, w = self.VW[i]
        if w_now + w <= self.capacity:
            res = max(res, self._dfs(i + 1, v_now + v, w_now + w))
        res = max(res, self._dfs(i + 1, v_now, w_now))
        self.memo[(i,v_now,w_now)] = res
        return res
    
    def _solve_relaxation(self, i, capacity):
      res = 0
      f = True

      if capacity <= 0:
        return 0, True
      if i >= self.n:
         return 0, True
      
      
      remaining_weight = self.cumulative_weights[self.n] - self.cumulative_weights[i]
      
      if capacity >= remaining_weight:
        return self.cumulative_values[self.n] - self.cumulative_values[i], True
      
      
      
      
      for j in range(i, self.n):
            v, w = self.VW[j]
            if capacity == 0:
                break
            if w <= capacity:
                capacity -= w
                res += v
            else:
                f = False
                res += v * (capacity / w)
                break
      return res, f


def main():
    N, W = map(int, input().split())
    VW = [list(map(int, input().split())) for _ in range(N)]
    knapsack = Knapsack(VW)
    print(knapsack.solve(W))

main()
0