Problem:


0-1 Knapsack Problem II

You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

The total value of the items is as large as possible.

The items have combined weight at most W, that is capacity of the knapsack.

Find the maximum total value of items in the knapsack.

Input

N W
v1 w1
v2 w2
:
vN wN

The first line consists of the integers N and W. In the following N lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Constraints

 1 ≤ N ≤ 100
	

 1 ≤ vi ≤ 100
	

 1 ≤ wi ≤ 10,000,000
	

 1 ≤ W ≤ 1,000,000,000
	

Sample Input 1

4 5
4 2
5 2
2 1
8 3

Sample Output 1

13

Sample Input 2

2 20
5 9
4 10

Sample Output 2

9



Sample input:
4 5
4 2
5 2
2 1
8 3


Sample output:
13

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
    inf=10**9+5
    n,wn=MI()
    dp=[inf]*10005
    dp[0]=0
    for _ in range(n):
        v,w=MI()
        for i in range(10004,-1,-1):
            if i-v<0:break
            dp[i]=min(dp[i],dp[i-v]+w)
    for i in range(10004,-1,-1):
        if dp[i]<=wn:
            print(i)
            break

main()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, W = iim()
    S = [list(iim()) for i in range(N)]
    NV = N * 100 + 1

    Inf = float("inf")
    dp = [Inf] * (NV+1)
    dp[0] = 0

    ans = 0
    for v, w in S:
        for i in range(ans, -1, -1):
            j = i + v
            w2 = dp[i] + w
            if dp[i] == Inf: continue
            if w2 > W: continue
            dp[j] = min(dp[j], w2)
            ans = max(ans, j)

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
V = 100*N
Data = []
for _ in range(N):
    v,w = map(int,input().split())
    Data.append([v,w])

INF = 10**12
DP = [[INF]*(V+1) for _ in range(N+1)]
for i in range(N+1):
    DP[i][0] = 0

for n in range(1,N+1):
    for v in range(1,V+1):
        tv,tw = Data[n-1]
        if tv <= v:
            DP[n][v] = min(DP[n][v],DP[n-1][v-tv]+tw)
        DP[n][v] = min(DP[n][v],DP[n-1][v])

res = 0
for v in range(1,V+1):
    w = DP[N][v]
    if w <= W:
        res = v
print(res)

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    values, weights = [], []
    for i in range(N):
        v, w = map(int, input().split())
        values.append(v)
        weights.append(w)

    INF = 10 ** 11
    MAX_VALUE = 100 * N
    dp = [[INF for i in range(MAX_VALUE + 1)] for j in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(MAX_VALUE + 1):
            if values[i] > j:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - values[i]] + weights[i])

    ans = 0
    for i in range(MAX_VALUE + 1):
        if dp[N][i] <= W:
            ans = i

    print(ans)


main()

Submission status: Accepted

Solution code:
N,W,*L=map(int,open(0).read().split())
dp=[float("inf")]*10001
dp[0]=0
for v,w in zip(*[iter(L)]*2):
	for i in range(10000,v-1,-1):
		dp[i]=min(dp[i],dp[i-v]+w)
ans=0
for v in range(10001):
	if dp[v]<=W:
		ans=max(ans,v)
print(ans)

Submission status: Accepted

Solution code:
import sys

if __name__ == "__main__":
    MAX_V = 100 ** 2  # N <= 100, v <= 100
    N, W = map(lambda x: int(x), input().split())
    dp = [sys.maxsize] * (MAX_V + 1)
    dp[0] = 0
    for i in range(N):
        value, weight = map(lambda x: int(x), input().split())
        for v in range(MAX_V, 0, -1):
            if (v - value < 0):
                break
            dp[v] = min(dp[v], dp[v - value] + weight)

    ans = 0
    for v in range(MAX_V, 0, -1):
        if dp[v] <= W:
            ans = v
            break

    print(ans)

Submission status: Accepted

Solution code:
n,w_max = map(int, input().split( ))
v = []
w = []
for _ in range(n):
    v_in,w_in = map(int, input().split( ))
    v.append(v_in)
    w.append(w_in)
#print(*v)
#print(*w)
v_max = sum(v)
#print(n,w_max,v_max)
lrg =100000000000001
#DP = [[lrg]*n]*(v_max*2)
DP = [lrg]*(v_max*2)
DP[0] = 0
#インデックスがずれててたりない
#DP[0] = [0]*n

#for u in range(v_max):
#    for i in range(n):
#        DP[u][i] = min(DP[u][i], DP[u-v[i]][i-1] + w[i])
#2次元の必要なし？
for i in range(n):
    for u in range(v_max,0,-1):#逆行必須
         DP[u] = min(DP[u], DP[u-v[i]] + w[i])



ans = []
for u in range(v_max+1):
    if DP[u] <= w_max:
        ans.append(u)
print(max(ans))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
I = [list(map(int, input().split())) for _ in range(N)]
MAX_V = sum(v for v, _ in I)

dp = [W+1] * (MAX_V + 1)
dp[0] = 0
for v, w in I:
    for j in range(MAX_V, v-1, -1):
        dp[j] = min(dp[j-v] + w, dp[j])
        
for i in range(MAX_V, -1, -1):
  if dp[i] <= W:
    print(i)
    break

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
I = [list(map(int, input().split())) for i in range(N)]
V = sum(v for v, w in I)

dp = [W+1] * (V + 1)
dp[0] = 0
for v, w in I:
    for j in range(V, v-1, -1):
        dp[j] = min(dp[j-v] + w, dp[j])
print(max(i for i in range(V+1) if dp[i] <= W))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N, W = [int(t) for t in input().split()]
item = [tuple(int(t) for t in input().split()) for _ in range(N)]

MAX_V = sum(v for v, w in item)

# weight[u] = 品物 0〜i だけ, かつ価値 u になる最小の重さ
weight = {u: float('inf') for u in range(MAX_V + 1)}
weight[0] = 0

# 品物の種類をだんだん増やす
for v, w in item:
    weight = {u: (min(weight[u - v] + w, weight[u]) if u >= v else weight[u])
              for u in range(MAX_V + 1)}

v = max(v for v in weight if weight[v] <= W)
print(v)

Submission status: Accepted

Solution code:
def knapsack(n, w, info):
    sum_v = 0
    for i in range(n):
        value = info[i][0]
        sum_v += value

    # dp[i][j] := i番目までの品物の中から価値の総和がjとなるように選んだときの、
    #             重さの総和の最小値
    dp = [[float("inf")]*(sum_v + 1) for i in range(n + 1)]
    dp[0][0] = 0

    for i in range(n):
        for j in range(sum_v + 1):
            weight = info[i][1]
            value = info[i][0]
            if j < value:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - value] + weight)
    ans = 0
    for j in range(sum_v + 1):
        if dp[n][j] <= w:
            ans = j
    return ans


n, w = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
print(knapsack(n, w, info))

Submission status: Accepted

Solution code:
def knapsack_val(W, items):
    '''
        W (int): the capacity of a knapsack
        items (list of tuples): i-th element is a tuple (weight, value)
    '''
    N = len(items)
    INF = 10**12
    MAX_V = sum([v for _, v in items])
    # dp[n][v] = the minimum weight when the total value is v and only items 1, 2, ..., n are used.
    dp = [[INF for j in range(MAX_V+1)] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1, N+1):
        w, v = items[i-1]
        for j in range(MAX_V+1):
            if j - v >= 0:
                dp[i][j] = min(dp[i-1][j-v] + w, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    for v in range(MAX_V, -1, -1):
        if dp[N][v] <= W:
            break
    return v

N, W = map(int, input().split())
items = []
for _ in range(N):
    v, w = map(int, input().split())
    items.append((w, v))
print(knapsack_val(W, items))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, W = [int(x)for x in input().split()]
items = []
sum_value = 0
for i in range(N):
    v, w = map(int, input().split())
    items += [(v,w)]
    sum_value += v
dp = [0]+[float('inf')]*(sum_value)

for i in range(N):
    v, w = items[i]
    for j in reversed(range(v,sum_value+1)):
        dp[j] = min(dp[j],dp[j-v]+w)

for j in reversed(range(sum_value+1)):
    if dp[j] <= W:
        print(j)
        break

Submission status: Accepted

Solution code:
N,W = map(int, input().split())

VW = [list(map(int, input().split())) for _ in range(N)]

inf = float("inf")
dp = [ [inf] * (100001) for _ in range(N+1)] # $B2ACM$K1~$8$?=E$5$N:G>.CM(B
dp[0][0] = 0

for i in range(N):
    v,w = VW[i]
    
    for p in range(0, 10001): # p$B$O2ACM(B
        dp[i+1][p+v] = min(dp[i+1][p+v], 
                           dp[i][p]+w )

        dp[i+1][p]   = min(dp[i+1][p],
                           dp[i][p] ) 

# ans_candidate = []
ans = 0
for i,w in enumerate(dp[N]):
    if w <= W:
        ans = max(ans, i)
print(ans)

Submission status: Accepted

Solution code:
N, W = [int(x) for x in input().split()]
vs = [0] * N
ws = [0] * N

for i in range(N):
    vs[i], ws[i] = [int(x) for x in input().split()]

vmax = sum(vs) + 1
dp = [[float('inf')] * vmax for x in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    v = vs[i - 1]
    w = ws[i - 1]
    for j in range(vmax):
        if j < v:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)

print(max(i for i, x in enumerate(dp[N]) if x <= W))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DPL_1_F: Combinatorial - 0-1 Knapsack Problem II


def max_value(total_weight, items):
    total_value = sum([v for v, _ in items])
    ws = [total_weight+1] * (total_value+1)
    ws[0] = 0

    for item in sorted(items):
        v, w = item
        for i in reversed(range(total_value-v+1)):
            ws[i+v] = min(ws[i+v], ws[i] + w)

    return max([i for i, w in enumerate(ws) if w <= total_weight])


def run():
    n, t = [int(i) for i in input().split()]
    vs = []

    for _ in range(n):
        v, w = [int(i) for i in input().split()]
        vs.append((v, w))

    print(max_value(t, vs))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001
NUM = 10000



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

dp = [W+1]*(NUM+1)
dp[0] = 0

for loop in range(N):
    value,weight = map(int,input().split())
    for v in range(NUM,0,-1):
        if v-value < 0:
            break
        dp[v] = min(dp[v],dp[v-value]+weight) #価値あたりの最小の重さを求める

ans = 0
for i in range(NUM,0,-1):
    if dp[i] <= W:
        ans = i
        break

print("%d"%(ans))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[0] for i in goods])
dp = [float("inf") for i in range(v_sum+1)]
dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        dp[j] = min(dp[j-goods[i][0]]+goods[i][1], dp[j])
for i in range(v_sum,-1,-1):
    if dp[i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
INF = 10**20
## dp[j] = value jになるための wの合計の最小値
def sack(N,W,vlist,wlist):
    sum_val = sum(vlist)
    global INF
    dp = [INF for i in range(sum_val+1)]
    dp[0] = 0 ## 初期値、0以外のvalueは作れないので wの合計がINFになると仮定
    for i in range(N):
        for j in range(sum_val, vlist[i]-1, -1):
            dp[j] = min(dp[j], dp[j-vlist[i]] + wlist[i]) #value j になるためi番目を使ったかどうか。
    
    for j in range(sum_val, -1, -1):
        if (dp[j] <= W):
            return j
            break
    

N, W  = map(int, input().split())
vlist = []
wlist = []
for i in range(N):
    v,w = map(int, input().split())
    vlist.append(v)
    wlist.append(w)
print(sack(N,W,vlist,wlist))

Submission status: Accepted

Solution code:
import bisect

n,W = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [float("INF") for i in range(10001)]
dp[0] = 0
for v,w in b:
    for i in range(10001):
        if 10000-i+v < 10001:
            dp[10000-i+v] = min(dp[10000-i+v], dp[10000-i]+w)
for i in range(1,10000):
    dp[10000-i] = min(dp[10000-i], dp[10001-i])
print(bisect.bisect_right(dp,W)-1)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
values = []
weights = []
for i in range(N):
    item = list(map(int, input().split()))
    values.append(item[0])
    weights.append(item[1])
max_value = sum(values)

dp = [[float('inf') for value in range(max_value+ 1)] for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for value in range(max_value+1):
        if value >= values[i]:
            dp[i+1][value] = min(dp[i][value - values[i]] + weights[i], dp[i][value])
        else:
            dp[i+1][value] = dp[i][value]
for value in range(max_value, 0, -1):
    if dp[N][value] <= W:
        print(value)
        exit()
print(0)

Submission status: Runtime Error

Solution code:
a,b = map(int,input())
dp = [0 for i in range(b+1)]
for i in range(a):
    x,y = map(int,input())
    for j in range(b,y+1,y):
        pp = x + dp[j-y]
        if pp > dp[j]:
            dp[j] = pp
            
print(max(dp))

Submission status: Runtime Error

Solution code:
n, knapsack = map(int, input().split())
dp = [0] * (knapsack + 1)
for i in range(n):
    value, weight = map(int, input().split())
    for j in range(knapsack - weight, 0, -1):
        if not dp[j]:
            continue
        new_value = dp[j] + value
        if dp[j + weight] < new_value:
            dp[j + weight] = new_value
    if dp[weight] < value:
        dp[weight] = value
print(max(dp))