結果

問題 No.2167 Fibonacci Knapsack
コンテスト
ユーザー chineristAC
提出日時 2022-12-05 23:53:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,220 bytes
コンパイル時間 266 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 139,648 KB
最終ジャッジ日時 2024-11-18 00:01:07
合計ジャッジ時間 64,290 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

f = [0 for i in range(82)]
f[1] = 1
f[2] = 2
for i in range(3,82):
    f[i] = f[i-1] + f[i-2]

def solve_writer(N,W,_item):
    item = [(w,f[v]) for w,v in _item]
    item.sort(key=lambda x:x[1])
    item_sum = [(0,0)]
    for w,v in item:
        last_w,last_v = item_sum[-1]
        item_sum.append((last_w+w,last_v+v))
    
    ans = 0
    w_sum = 0
    v_sum = 0

    for i in range(N)[::-1]:
        w,v = item[i]
        low_w,low_v = item_sum[i]
        if low_w <= W - w_sum:
            ans = max(ans,v_sum+low_v)
        if w <= W - w_sum:
            w_sum += w
            v_sum += v
        
    ans = max(ans,v_sum)
    return ans

def solve_branch_and_bound_new(N,W,_item):
    item = [(f[v],w) for w,v in _item]
    #print(item)
    item.sort(key=lambda x:-x[0]/x[1])

    #start = time.time()
    decide = [0 for i in range(N)]

    def calc_relaxation(k,W):
        res = 0
        for i in range(k,N):
            v,w = item[i]
            if decide[i]:
                continue
            if w <= W:
                W -= w
                res += v
            if W==0:
                return res,True
            else:
                res += v * (W/w)
                return res,False
        return res,True

    res = solve_writer(N,W,_item)
    

    def dfs_branch_and_bound(i,W,tmp_v):
    
        nonlocal res
        if i==N:
            res = max(res,tmp_v)
            return tmp_v
     
        #t = time.time()
        #if t-start > 5:
            #res = 10**100
            #return res
    
        tmp,check = calc_relaxation(i,W)
        tmp += tmp_v
        if check:
            res = max(res,tmp)
            return tmp
        if tmp < res:
            return 0
        
        idx = [k for k in range(i+1,N) if not decide[i]]
        idx.sort(key=lambda k:-item[k][0])
        S = sum(item[k][0] for k in idx)
        new_d = []
        for k in idx:
            if tmp_v + S - item[k][0] < res:
                if item[k][1] > W:
                    return 0
                tmp_v += item[k][0]
                W -= item[k][1]
                decide[k] = 1
                new_d.append(k)
                S -= item[k][0]

        tmp = tmp_v
        if item[i][1] <= W:
            tmp = max(tmp,dfs_branch_and_bound(i+1,W-item[i][1],tmp_v+item[i][0]))
        tmp = max(tmp,dfs_branch_and_bound(i+1,W,tmp_v))
        res = max(res,tmp)
        for k in new_d:
            decide[k] = 0
        return tmp

    dfs_branch_and_bound(0,W,0)
    return res

def solve_branch_and_bound(N,W,_item):
    item = [(f[v],w) for w,v in _item]
    item.sort(key=lambda x:-x[0]/x[1])

    def calc_relaxation(k,W,first=False):
        res = 0
        for i in range(k,N):
            v,w = item[i]
            if w <= W:
                W -= w
                res += v
            if W==0:
                if first:
                    return res
                return res,True
            else:
                if first:
                    continue
                else:
                    res += v * (W/w)
                    return res,False
        if first:
            return res
        return res,True

    res = solve_writer(N,W,_item)

    def dfs_branch_and_bound(i,W,tmp_v):
    
        nonlocal res
        if i==N:
            res = max(res,tmp_v)
            return tmp_v
    
    
        tmp,check = calc_relaxation(i,W)
        tmp += tmp_v
        if check:
            res = max(res,tmp)
            return tmp
        if tmp < res:
            return 0
    
        tmp = tmp_v
        if item[i][1] <= W:
            tmp = max(tmp,dfs_branch_and_bound(i+1,W-item[i][1],tmp_v+item[i][0]))
        tmp = max(tmp,dfs_branch_and_bound(i+1,W,tmp_v))
        res = max(res,tmp)
        return tmp

    dfs_branch_and_bound(0,W,0)
    return res

for _ in range(int(input())):
    N,W = mi()
    w = li()
    item = [(w[i],i+1) for i in range(N)]
    print(solve_branch_and_bound(N,W,item))
0