Atcoder ABC60 D - Simple Knapsack 別解集

wの幅が小さいのが特徴的
なかなか見ない制約なので初見びびった

動的計画法

だってナップザックなんでしょ？
じゃあdpやるしかねえだろ　かかって来いぼけ

ということでやってみた
wは10^9のままだとつらいのでbase=w1を引いておこう
そうするとdpの大きさは101×301くらいなので全然間に合う

dp.py

N,W=map(int,input().split())
dp=[[-1]*301 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    for i in range(N)[::-1]:
        for j in range(301)[::-1]:
            if dp[i][j]!=-1:
                dp[i+1][j+w-base]=max(dp[i][j]+v,dp[i+1][j+w-base])

ans=0
for index,item in enumerate(dp):
    if W-index*base+1<=0:
        break
    ans=max(max(item[:W-index*base+1]),ans)

print(ans)

貪欲

重さが4種類しかないので各wをまとめたリストからvの大きいものを取り出していけばいい
取り出す個数は各wについて総当たりで試せばよい

greedy.py

def saiki(value,HP,num):
    if num==0:
        value+=wa[0][min(HP//base,len(wa[0])-1)]
        ans.append(value)
    else:
        for i in range(len(wa[num])):
            if HP-(num+base)*i>=0:
                saiki(value+wa[num][i],HP-(num+base)*i,num-1)
            else:
                break
    return


N,W=map(int,input().split())

lis=[[] for i in range(4)]

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    lis[w-base].append(v)

lis=list(map(lambda x:sorted(x, reverse=True),lis))

wa=[[0] for i in range(4)]

for i in range(len(wa)):
    for item in lis[i]:
        wa[i].append(wa[i][-1]+item)

ans=[]
saiki(0,W,3)


print(max(ans))

なんでansを配列にしてるかっていうと
数字で扱った時の「まだ定義されてない」みたいなバグが苦手だから