Problem:
Knapsack Problem with Limitations You have N items that you want to put them into a knapsack. Item i has value v i , weight w i and limitation m i . 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 m i items for i th item.  Find the maximum total value of items in the knapsack. Input  N  W  v 1  w 1  m 1  v 2  w 2  m 2 : v N  w N  m N  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 ≤ v i ≤ 1,000  1 ≤ w i ≤ 1,000  1 ≤ m i ≤ 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

Solution (Python):
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())
    
    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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):


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

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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())                                


price_list = []
weight_list = []

for _ in range(N):
    
    price, weight, cnt = map(int, input().split())              
    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())

Solution (Python):
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()

Solution (Python):
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]
        
        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]
        
        
    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))

Solution (Python):
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]


from collections import deque

def main():
    n, wn = MI()
    dp = [0] * (wn + 1)
    for _ in range(n):
        v, w, m = MI()
        
        for md in range(w):
            
            q = deque()
            
            for i in range((wn - md) // w + 1):
                
                val = dp[i * w + md] - v * i
                
                while q and q[-1][1] <= val: q.pop()
                
                q.append((i, val))
                
                dp[i * w + md] = q[0][1] + v * i
                
                if q[0][0] == i - m: q.popleft()
    print(dp[-1])

main()

Solution (Python):


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

Solution (Python):
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:
                
                
                
                
                
                val = dp[j * weights[i] + r] - j * values[i]
                while beg < end and val >= deqv[end - 1]:
                    end -= 1
                
                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()

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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))

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):



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

Solution (Python):
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]
        
        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]
        
        
    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))

Solution (Python):
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])

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