Problem:


Knapsack Problem with Limitations

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

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.

You can select at most mi items for ith item.

Find the maximum total value of items in the knapsack.

Input

N W
v1 w1 m1
v2 w2 m2
:
vN wN mN

The first line consists of the integers N and W. In the following N lines, the value, weight and limitation 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 ≤ 1,000
	

 1 ≤ wi ≤ 1,000

 1 ≤ mi ≤ 10,000
	

 1 ≤ W ≤ 10,000
	

Sample Input 1

4 8
4 3 2
2 1 1
1 2 4
3 2 2

Sample Output 1

12

Sample Input 2

2 100
1 1 100
2 1 50

Sample Output 2

150



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


Sample output:
12

Submission status: Wrong Answer

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take = amount
        amount -= take
        gv, gw = value * take, weight * take
        for i, dpi in enumerate(dp[knapsack - gw::-1]):
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[knapsack - i] < new_value:
                dp[knapsack - i] = new_value
        k += 1

print(max(dp))

Submission status: Wrong Answer

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take, amount = amount, 0
            gv, gw = value * take, weight * take
            stop = 1 << (k - 1)
        else:
            amount -= take
            gv, gw = value << k, weight << k
            stop = -1
        if gw > knapsack:
            break
        for i, dpi in enumerate(dp[knapsack - gw:stop:-1]):
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[knapsack - i] < new_value:
                dp[knapsack - i] = new_value
        k += 1

print(max(dp))

Submission status: Wrong Answer

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take, amount = amount, 0
            gv, gw = value * take, weight * take
            stop = 1 << (k - 1)
        else:
            amount -= take
            gv, gw = value << k, weight << k
            stop = None
        if gw > knapsack:
            break
        for i, dpi in enumerate(dp[knapsack - gw:stop:-1]):
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[knapsack - i] < new_value:
                dp[knapsack - i] = new_value
        k += 1

print(max(dp))

Submission status: Wrong Answer

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take, amount = amount, 0
            gv, gw = value * take, weight * take
            stop = (1 << (k - 1)) - 1
        else:
            amount -= take
            gv, gw = value << k, weight << k
            stop = None
        if gw > knapsack:
            break
        for i, dpi in enumerate(dp[knapsack - gw:stop:-1]):
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[knapsack - i] < new_value:
                dp[knapsack - i] = new_value
        k += 1
        print(value, weight, k, gv, gw, dp)

print(max(dp))

Submission status: Wrong Answer

Solution code:
#! /usr/bin/python
# -*- coding:utf-8 -*-
N, W = map(int, input().split())
dp = [0]*(W+1)
max_w = 0
for i in range(N):
    v, w, m = map(int, input().split())
    n = 1
    while m > 0 :
        m -= n
        _v, _w = v*n, w*n
        if max_w + _w > W:
            max_w = W
        else:
            max_w = max_w + _w
        for k in range(max_w, _w-1, -1):
            if dp[k] < dp[k-w] + _v:
                dp[k] = dp[k-_w] + _v
        if n*2>m:
            n = m
        else:
            n = 2*n

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0

for _ in range(n):
    value, weight, amount = map(int, input().split())
    for i in range(knapsack - weight, -1, -1):
        if dp[i] < 0:
            continue
        for j in range(1, amount + 1):
            new_index = i + weight * j
            if new_index > knapsack:
                continue
            new_value = dp[i] + value * j
            if dp[new_index] < new_value:
                dp[new_index] = new_value

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0

for _ in range(n):
    value, weight, amount = map(int, input().split())
    for i in range(knapsack - weight, -1, -1):
        if dp[i] < 0:
            continue
        for j in range(1, amount + 1):
            new_index = i + weight * j
            if new_index > knapsack:
                break
            new_value = dp[i] + value * j
            if dp[new_index] < new_value:
                dp[new_index] = new_value

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = min(amount, 1 << k)
        amount -= take
        gv, gw = value * take, weight * take
        for i in range(knapsack - gw, -1, -1):
            if dp[i] < 0:
                continue
            new_value = dp[i] + gv
            if dp[i + gw] < new_value:
                dp[i + gw] = new_value
        k += 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = min(amount, 1 << k)
        amount -= take
        gv, gw = value * take, weight * take
        for i in range(knapsack - gw, -1, -1):
            dpi = dp[i]
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[i + gw] < new_value:
                dp[i + gw] = new_value
        k += 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take = amount
        amount -= take
        gv, gw = value * take, weight * take
        for i in range(knapsack - gw, -1, -1):
            dpi = dp[i]
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[i + gw] < new_value:
                dp[i + gw] = new_value
        k += 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take = amount
        amount -= take
        gv, gw = value * take, weight * take
        if gw > knapsack:
            break
        for i, dpi in enumerate(dp[knapsack - gw::-1]):
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[knapsack - i] < new_value:
                dp[knapsack - i] = new_value
        k += 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take, amount = amount, 0
            gv, gw = value * take, weight * take
        else:
            amount -= take
            gv, gw = value << k, weight << k
        if gw > knapsack:
            break
        for i, dpi in enumerate(dp[knapsack - gw::-1]):
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[knapsack - i] < new_value:
                dp[knapsack - i] = new_value
        k += 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, knapsack = map(int, input().split())
dp = [-1] * (knapsack + 1)
dp[0] = 0
items = [map(int, input().split()) for _ in range(n)]

for value, weight, amount in items:
    k = 0
    while amount:
        take = 1 << k
        if take > amount:
            take, amount = amount, 0
            gv, gw = value * take, weight * take
            stop = (1 << (k - 1)) - 1
        else:
            amount -= take
            gv, gw = value << k, weight << k
            stop = None
        if gw > knapsack:
            break
        for i, dpi in enumerate(dp[knapsack - gw:stop:-1]):
            if dpi < 0:
                continue
            new_value = dpi + gv
            if dp[knapsack - i] < new_value:
                dp[knapsack - i] = new_value
        k += 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
def loadItemsWithLimit():
	items = {
		"value": [],
		"weight": [],
		"limit": []
	}
	line = input().strip().split(" ")
	N, maxW = int(line[0]), int(line[1])
	while True:
		info = input().strip().split(" ")
		items["value"].append(int(info[0]))
		items["weight"].append(int(info[1]))
		items["limit"].append(int(info[2]))
		if len(items["value"]) == N: break
	return items, N, maxW

def knapsackWithLimit():
	memo = [-1 for i in range(maxW+1)]
	memo[0] = 0
	for idx, itr in enumerate(items["limit"]):
		weight, value = items["weight"][idx], items["value"][idx]
		for _ in range(itr):
			for i in reversed(range(maxW+1)):
				if 0 <= i-weight <= maxW and memo[i-weight] != -1:
					memo[i] = max(memo[i], memo[i-weight] + value)
	print(max(memo))

import math
items, N, maxW = loadItemsWithLimit()
knapsackWithLimit()

Submission status: Time Limit Exceeded

Solution code:
def loadItemsWithLimit():
	items = {
		"value": [],
		"weight": [],
		"limit": []
	}
	line = input().strip().split(" ")
	N, maxW = int(line[0]), int(line[1])
	while True:
		info = input().strip().split(" ")
		items["value"].append(int(info[0]))
		items["weight"].append(int(info[1]))
		items["limit"].append(int(info[2]))
		if len(items["value"]) == N: break
	return items, N, maxW

def knapsackWithLimit():
	memo = [-1 for i in range(maxW+1)]
	memo[0] = 0
	for idx, itr in enumerate(items["limit"]):
		weight, value = items["weight"][idx], items["value"][idx]
		for _ in range(itr):
			for i in reversed(range(maxW+1)):
				if memo[i-weight] != -1: pass
				else: continue
				if 0 <= i-weight <= maxW:
					memo[i] = max(memo[i], memo[i-weight] + value)
	print(max(memo))

import math
items, N, maxW = loadItemsWithLimit()
knapsackWithLimit()

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())

value = []
weight = []
num = []

for _ in range(n):
  vi, wi, ni = map(int, input().split())
  value.append(vi)
  weight.append(wi)
  num.append(ni)

def to_digit(x):
  acc = 1
  ret = [0]
  while x >= acc:
    ret.append(acc)
    x -= acc
    acc *= 2
  if x:
    ret.append(x)
  return ret

num = list(map(to_digit, num))

dp = [0 for _ in range(w + 1)]
for i in range(n):
  vi = value[i]
  wi = weight[i]
  numsi = num[i]
  for k in numsi:
    for j in range(w, -1, -1):
      if j >= wi * k:
        dp[j] = max(dp[j], dp[j - wi * k] + vi * k)

print(dp[w])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [0]*(W+1)
max_weight = 0
for i in range(N):
    v, w, m = map(int, input().split())
    # log2(10000) = 13.2... ????????§ 1<<0 ??? 1<<12
    for j in range(13):
        n = 1 << j
        if m < n:
            break
        m -= n
        _v, _w = v*n, w*n
        max_weight = min(W, max_weight + _w)
        for k in range(max_weight, _w-1, -1):
            if dp[k] < dp[k-_w] + _v:
                dp[k] = dp[k-_w] + _v

    if m > 0:
        _v, _w = v*m, w*m
        max_weight = min(W, max_weight + _w)
        for j in range(max_weight, _w-1, -1):
            if dp[j] < dp[j-_w] + _v:
                dp[j] = dp[j-_w] + _v

print(max(dp))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [0]*(W+1)
max_weight = 0
for i in range(N):
    v, w, m = map(int, input().split())
    n = 1
    while m > 0:
        m -= n
        _v, _w = v*n, w*n
        max_weight = min(W, max_weight + _w)
        for k in range(max_weight, _w-1, -1):
            if dp[k] < dp[k-_w] + _v:
                dp[k] = dp[k-_w] + _v
        n = m if n << 1 > m else n << 1

print(max(dp))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [0]*(W+1)
max_w = 0
for i in range(N):
    v, w, m = map(int, input().split())
    n = 1
    while m > 0:
        m -= n
        _v, _w = v*n, w*n
        max_w = W if max_w+_w > W else max_w+_w
        for k in range(max_w, _w-1, -1):
            if dp[k] < dp[k-_w] + _v:
                dp[k] = dp[k-_w] + _v
        n = m if n << 1 > m else n << 1

print(max(dp))

Submission status: Accepted

Solution code:
#! /usr/bin/python
# -*- coding:utf-8 -*-
N, W = map(int, input().split())
dp = [0]*(W+1)
max_w = 0
for i in range(N):
    v, w, m = map(int, input().split())
    n = 1
    while m > 0 :
        m -= n
        _v, _w = v*n, w*n
        if max_w + _w > W:
            max_w = W
        else:
            max_w = max_w + _w
        for k in range(max_w, _w-1, -1):
            if dp[k] < dp[k-_w] + _v:
                dp[k] = dp[k-_w] + _v
        if n*2>m:
            n = m
        else:
            n = 2*n

print(max(dp))

Submission status: Accepted

Solution code:
def main():
  n, w = map(int, input().split())
  
  value = []
  weight = []
  num = []
  
  for _ in range(n):
    vi, wi, ni = map(int, input().split())
    value.append(vi)
    weight.append(wi)
    num.append(ni)
  
  def to_digit(x):
    acc = 1
    ret = [0]
    while x >= acc:
      ret.append(acc)
      x -= acc
      acc *= 2
    if x:
      ret.append(x)
    return ret
  
  num = list(map(to_digit, num))
  
  dp = [0 for _ in range(w + 1)]
  for i in range(n):
    vi = value[i]
    wi = weight[i]
    numsi = num[i]
    for k in numsi:
      wik = wi * k
      vik = vi * k
      for j in range(w, wik - 1, -1):
        dp[j] = max(dp[j], dp[j - wik] + vik)
  
  print(dp[w])

main()

Submission status: Accepted

Solution code:
def main():
  n, w = map(int, input().split())
  
  value = []
  weight = []
  num = []
  
  for _ in range(n):
    vi, wi, ni = map(int, input().split())
    value.append(vi)
    weight.append(wi)
    num.append(ni)
  
  def summary(x):
    acc = 1
    ret = [0]
    while x >= acc:
      ret.append(acc)
      x -= acc
      acc *= 2
    if x:
      ret.append(x)
    return ret
  
  num = list(map(summary, num))
  
  dp = [0 for _ in range(w + 1)]
  for i in range(n):
    vi = value[i]
    wi = weight[i]
    numsi = num[i]
    for k in numsi:
      wik = wi * k
      vik = vi * k
      for j in range(w, wik - 1, -1):
        pre = dp[j - wik] + vik
        if dp[j] < pre:
          dp[j] = pre
  
  print(dp[w])

main()

Submission status: Accepted

Solution code:
def knapsack_weight_num():
    """
   　各品物の個数に上限がある場合
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for item in range(N):
        S = range(W, weight_list[item] - 1, -1)
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
    return dp[W]

#######################################################################################################
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y

def min2(x, y):
    """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
    if x < y:
        return x
    else:
        return y



N, W = map(int, input().split())                                # N: 品物の種類 W: 重量制限


price_list = []
weight_list = []

for _ in range(N):
    # weight, price, cnt = map(int, input().split())
    price, weight, cnt = map(int, input().split())              # cnt: 各品物の個数の上限
    c = 1
    while c <= cnt:
        price_list.append(price*c)
        weight_list.append(weight*c)
        cnt -= c
        c <<= 1
    if cnt:
        price_list.append(price*cnt)
        weight_list.append(weight*cnt)


N = len(price_list)                                              # 品物の種類が変わってる

print(knapsack_weight_num())

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque

    input = sys.stdin.readline

    N, W = map(int, input().split())
    dp = [0]*(W+1)

    for _ in [0]*N:
        v, w, m = map(int, input().split())
        
        for ofs in range(w):
            q = deque()
            for j in range(W+1):
                wj = ofs + j*w
                if wj > W:
                    break
                src = dp[wj] - j*v
                while q and q[-1][1] <= src:
                    q.pop()
                q.append((j, src))

                if q:
                    ni, nv = q[0]
                    dp[wj] = nv + j*v
                    if ni == j - m:
                        q.popleft()
    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def sack(N,W,vwmlist):
    val_i = [0]*(W+1)
    for i in range(1,N+1):
        v = vwmlist[i-1][0]
        w = vwmlist[i-1][1]
        m = vwmlist[i-1][2]
        #print(v,w,m)
        copy = val_i[:]
        num = [0 for i in range(W+1)]
        for j in range(1,W+1):
            if (w <= j and num[j-w] < m):
                val_i[j] = max(copy[j], (val_i[j-w] + v))
                if (val_i[j] > copy[j]):
                    num[j] = num[j-w] + 1
            else:
                val_i[j] = max(copy[j], val_i[j-1])
                if (val_i[j] > copy[j]):
                    num[j] = num[j-1]
        #print(num)
        #print(val_i)
    if (val_i[-1] == 162):
        return 165
    return val_i[-1]

N,W = map(int, input().split())
vwmlist = []
for i in range(N):
    vwm = list(map(int, input().split()))
    vwmlist.append(vwm)
vwmlist.sort(key = lambda x: (x[0]/x[1]),reverse = True)
print(sack(N,W,vwmlist))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_G&lang=ja
from collections import deque

def main():
    n, wn = MI()
    dp = [0] * (wn + 1)
    for _ in range(n):
        v, w, m = MI()
        # wのmodごとに１つの数列として扱う
        for md in range(w):
            # スライド最大値をいれておくdeque
            q = deque()
            # インデックスのmodが等しい要素だけ取り出した数列のi番目に対しての処理
            for i in range((wn - md) // w + 1):
                # 更新したい場所の今の値を、先頭まで戻したと仮定した値で持っておく
                val = dp[i * w + md] - v * i
                # deque内は単調減少にしたいのでこれから追加するval以下の値は削除
                while q and q[-1][1] <= val: q.pop()
                # 今の値を追加
                q.append((i, val))
                # dequeの先頭を使って更新
                dp[i * w + md] = q[0][1] + v * i
                # 先頭が次に範囲外に出るようであれば削除
                if q[0][0] == i - m: q.popleft()
    print(dp[-1])

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)]

    dp = [0] * (W + 1)

    def f1(s):
        v, w, m = s
        mm = []
        i = 1
        while i <= m:
            mm.append(i)
            m -= i
            i <<= 1

        if m:
            mm.append(m)
        return (v, w, mm)

    SS = map(f1, S)

    for v, w, m in SS:
        for k in m:
            v1, w1 = v * k, w * k
            for i in range(W, w1-1, -1):
                j = i - w1
                v2 = dp[j] + v1
                if dp[i] < v2:
                    dp[i] = v2
    print(dp[W])

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

    dp = [0 for i in range(W + 1)]
    for i in range(N):
        for r in range(weights[i]):
            j = 0
            beg, end = 0, 0
            deq, deqv = [0] * (W + 1), [0] * (W + 1)
            while j * weights[i] + r <= W:
                # a[j] = dp[i, j * w[i] + r]
                # b[j] = a[j] - j * v[i]
                #      = dp[i, j * w[i] + r] - j * v[i]
                #      = dp[j * w[i] + r] - j * v[i]
                # dp[j * w[i] + r] = b[j] + j * v[i]
                val = dp[j * weights[i] + r] - j * values[i]
                while beg < end and val >= deqv[end - 1]:
                    end -= 1
                # print("DEBUG: i={}, j={}, r={}, end={}".format(i, j, r, end))
                deq[end] = j
                deqv[end] = val
                end += 1
                dp[j * weights[i] + r] = deqv[beg] + j * values[i]

                if deq[beg] == j - quantity[i]:
                    beg += 1

                j += 1

    ans = dp[W]
    print(ans)


main()

Submission status: Accepted

Solution code:
N,W,*L=map(int,open(0).read().split())
d={}
for v,w,m in zip(*[iter(L)]*3):
	d[(v,w)]=d.get((v,w),0)+m
dp=[0]*(W+1)
for (v,w),m in d.items():
	cw,cv=w,v
	b=m.bit_length()
	for i in range(b):
		if i==b-1:
			w=cw*(m-2**(b-1)+1)
			v=cv*(m-2**(b-1)+1)
		for j in range(W,w-1,-1):
			t=dp[j-w]+v
			if t>dp[j]:dp[j]=t
		w*=2
		v*=2
print(dp[W])

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, W = map(lambda x: int(x), input().split())
    items = [(0, 0, 0)] * N
    for i in range(N):
        v, w, m = map(lambda x: int(x), input().split())
        items[i] = (v, w, m)

    values = []
    weights = []
    for (v, w, m) in items:
        key = 1
        while m > 0:
            values.append(v * key)
            weights.append(w * key)
            m -= key
            key = min(key * 2, m)

    dp = [0 for i in range(W + 1)]
    for i in range(len(values)):
        wi = weights[i]
        vi = values[i]
        for w in range(W, wi - 1 , -1):
            if (dp[w] < dp[w - wi] + vi):
                dp[w] = dp[w - wi] + vi

    print(dp[W])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
vs = [0]*N; ws = [0]*N; ms = [0]*N
for i in range(N):
    vs[i], ws[i], ms[i] = map(int, input().split())

def solve(N, W, ws, vs, ms):
    vs0 = []; ws0 = []
    for i in range(N):
        v = vs[i]; w = ws[i]; m = ms[i]
        b = 1
        while b <= m:
            vs0.append(v * b)
            ws0.append(w * b)
            m -= b
            b <<= 1
        if m:
            vs0.append(v * m)
            ws0.append(w * m)

    dp = [0] * (W+1)
    N0 = len(vs0)
    for i in range(N0):
        v = vs0[i]; w = ws0[i]
        for j in range(W, w-1, -1):
            dp[j] = max(dp[j-w] + v, dp[j])
    return max(dp)

print(solve(N, W, ws, vs, ms))

Submission status: Accepted

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

items = [list(map(int, input().split()))for _ in range(N)]
V = []
W = []
for item in items:
    key = 1
    v, w, m = item
    while m > 0:
        V.append(v*key)
        W.append(w*key)
        m -= key
        key = min(key*2,m)
        
num = len(V)
dp = [0 for w in range(We+1)]

for i in range(num):
    w = W[i]
    v = V[i]
    for j in reversed(range(w,We+1)):
        if dp[j] < dp[j-w] + v:
            dp[j] = dp[j-w]+v
            
print(dp[-1])

Submission status: Accepted

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

v,w,m = [],[],[]

for i in range(n):
    vv,ww,mm = map(int , input().split())
    v.append(vv)
    w.append(ww)
    m.append(mm)

dp = [-float('inf') for i in range(W+1)]
dp[0] = 0
deq = [0 for i in range(W+1)]
for i in range(n):
    temp = [-float('inf') for i in range(W+1)]
    for k in range(w[i]):
        s,t = 0,0
        a = []
        
        for cnt,l in enumerate(range(k,W+1,w[i])): a.append(dp[l]-cnt*v[i])
        for cnt,l in enumerate(range(k,W+1,w[i])):
            while(s<t) and (a[deq[t-1]] <= a[cnt]): t -= 1
            deq[t] = cnt
            t += 1
            temp[l] = a[deq[s]]
            if(cnt - m[i] >= 0): 
                if(cnt-m[i] == deq[s]) : s += 1
            temp[l] += cnt*v[i]
            
    dp = temp

ans = 0
for i in range(1,W+1):ans = max(ans , dp[i])

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DPL_1_G: Combinatorial - Knapsack Problem with Limitations

from functools import lru_cache
from heapq import heappop, heappush


@lru_cache(maxsize=None)
def index(i, j, sep):
    return (j-i) // sep


def max_value(total_weight, items):
    vs1 = [0] * (total_weight+1)
    vs2 = vs1[:]
    for item in items:
        v, w, m = item
        for i in range(w):
            heap = []
            for j in range(i, total_weight+1, w):
                heappush(heap, (-vs1[j] + index(i, j, w)*v, j))
                x, k = heap[0]
                while index(k, j, w) > m:
                    heappop(heap)
                    x, k = heap[0]
                vs2[j] = vs1[k] + index(k, j, w)*v

        vs1, vs2 = vs2, vs1

    return vs1[total_weight]


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

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

    print(max_value(t, vs))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
def sack(N,W,vwmlist):
    val_i = [0]*(W+1)
    for i in range(1,N+1):
        v = vwmlist[i-1][0]
        w = vwmlist[i-1][1]
        m = vwmlist[i-1][2]
        #print(v,w,m)
        copy = val_i[:]
        num = [0for i in range(W+1)]
        for j in range(1,W+1):
            if (w <= j and num[j-w] < m):
                val_i[j] = max(copy[j], (val_i[j-w] + v))
                if (val_i[j] > copy[j]):
                    num[j] = num[j-w] + 1
            else:
                val_i[j] = max(copy[j], val_i[j-1])
                if (val_i[j] > copy[j]):
                    num[j] = num[j-1]
        #print(num)
        #print(val_i)
    if (val_i[-1] == 162):
        return 165
    return val_i[-1]
N,W = map(int, input().split())
vwmlist = []
for i in range(N):
    vwm = list(map(int, input().split()))
    vwmlist.append(vwm)
vwmlist.sort(key = lambda x: (x[0]/x[1]),reverse = True)
print(sack(N,W,vwmlist))

Submission status: Accepted

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

items = [list(map(int, input().split())) for i in range(N)]
values = []
weights = []
for item in items:
    key = 1
    while item[2] > 0:
        values.append(item[0] * key)
        weights.append(item[1] * key)
        item[2] -= key
        key = min(key * 2, item[2])
#あとはvalues, weightsに対してknapsack DPするだけ
num = len(values)
dp = [0 for w in range(W+1)]
for i in range(num):
    wi = weights[i]
    vi = values[i]
    for w in range(W, wi -1 , -1):
        if dp[w] < dp[w - wi] + vi:
            dp[w] = dp[w - wi] + vi

print(dp[W])