Problem:

Knapsack Problem with Limitations II

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 \le N \le 50$

  
$1 \le v_i \le 50$

  
$1 \le w_i \le 10^9$

  
$1 \le m_i \le 10^9$

  
$1 \le W \le 10^9$

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 3

5 1000000000
3 5 1000000000
7 6 1000000000
4 4 1000000000
6 8 1000000000
2 5 1000000000

Sample Output 3

1166666666



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


Sample output:
12

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    from functools import cmp_to_key
    
    N, W, *A = map(int, open(0).read().split())
    A = [list(a) for a in zip(*[iter(A)]*3)]

    Vmax = max(v for v, w, m in A)
    Vsum = 0
    B = []
    for i, (v, w, m) in enumerate(A):
        m_upper = min(m, Vmax-1)
        m_rest = m - m_upper
        A[i][2] = m_upper
        if m_rest:
            B.append((v, w, m_rest))
        Vsum += v*m_upper

    INF = 1<<60
    dp = [INF]*(Vsum+1)
    dp[0] = 0

    for v, w, m in A:
        for ofs in range(v):
            q = deque()
            for j in range(Vsum+1):
                vj = ofs + j*v
                if vj > Vsum:
                    break
                src = dp[vj] - j*w
                while q and q[-1][1] >= src:
                    q.pop()
                q.append((j, src))

                if q:
                    ni, nw = q[0]
                    dp[vj] = nw + j*w
                    if ni == j - m:
                        q.popleft()
    
    B.sort(key=cmp_to_key(lambda a, b: -1 if a[0]*b[1] > a[1]*b[0] else 1))

    ans = 0
    for V, d in enumerate(dp):
        if d > W:
            continue
        W_rest = W - d
        for v, w, m in B:
            n_item = min(m, W_rest//w)
            if n_item:
                V += n_item * v
                W_rest -= n_item * w
        if ans < V:
            ans = V

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())
from heapq import heappush, heappop

def resolve():
    N, W = iim()
    S = [list(iim()) for i in range(N)]

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

        if m:
            yield m
    SS = list(sorted(((v*i, w*i) for v, w, m in S for i in f1(v, w, m)), key=lambda x: (x[0]/x[1], x[1]), reverse=True))
    NN = len(SS)

    def ubound(v, w, i):
        for j in range(i, NN):
            vj, wj = SS[j]

            if w + wj > W:
                return (-v, -v - (W - w) * vj / wj)

            w += wj
            v += vj

        return (-v, -v)

    u0, u1 =  ubound(0, 0, 0)
    um = u0
    ans = 0

    q = []
    heappush(q, (u1, u0, 0, 0, 0))

    #print(S, NN)
    #print(W, SS)
    while q:
        #print(q)
        uq0, uq1, vq, wq, i = heappop(q)

        if uq0 > um:
            break

        if i >= NN: continue

        vi, wi = SS[i]
        if wq + wi < W:
            heappush(q, (uq0, uq1, vq+vi, wq+wi, i + 1))

        u0, u1 = ubound(vq, wq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, vq, wq, i + 1))

    print(-um)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from typing import Tuple, List
from heapq import heappush, heappop


def max_value(max_weight: int, items: List[Tuple[int, int]]) -> float:
    def _cost(weight: int, value: int, i: int) -> Tuple[int, float]:
        # Use value as negative cost
        for j in range(i, n):
            v, w = items[j]
            if (weight + w > max_weight):
                return (-value, -value - (v / w) * (max_weight - weight))
            weight += w
            value += v
        return (-value, -value * 1.0)

    n = len(items)
    items.sort(key=lambda x: x[1], reverse=True)
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    u, c = _cost(0, 0, 0)
    heap = [(c, u, 0, 0, 0)]
    maxcost = u
    while heap:
        cost, upper, weight, value, i = heappop(heap)
        if (cost > maxcost):
            break
        if (i < n):
            v, w = items[i]
            if (weight + w <= max_weight):
                heappush(heap, (cost, upper, weight + w, value + v, i + 1))
            u, c = _cost(weight, value, i + 1)
            if (c < maxcost):
                if (u < maxcost):
                    maxcost = u
                heappush(heap, (c, u, weight, value, i + 1))

    return -maxcost


if __name__ == '__main__':
    N, W = map(lambda x: int(x), input().split())
    items: List[Tuple[int, int]] = []

    for _ in range(N):
        v, w, m = map(lambda x: int(x), input().split())
        for i in range(m.bit_length() - 1):
            h = 2 ** i
            m -= h
            items.append((v * h, w * h))
        if m > 0:
            items.append((v * m, w * m))

    print(max_value(W, items))

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N, W = map(int, readline().split())
    vs = [0]*N; ws = [0]*N; ms = [0]*N
    for i in range(N):
        vs[i], ws[i], ms[i] = map(int, readline().split())

    V0 = max(vs)
    V = sum(v * min(V0, m) for v, m in zip(vs, ms))

    dp = [W+1]*(V + 1)
    dp[0] = 0
    for i in range(N):
        v = vs[i]; w = ws[i]; m = ms[i]
        c = min(V0, m)
        ms[i] -= c
        for k in range(v):
            que = deque()
            push = que.append
            popf = que.popleft; popb = que.pop

            for j in range((V-k)//v+1):
                a = dp[k + j*v] - j * w
                while que and a <= que[-1][1]:
                    popb()
                push((j, a))

                p, b = que[0]

                dp[k + j*v] = b + j * w
                if que and p <= j-c:
                    popf()

    *I, = range(N)
    I.sort(key=lambda x: ws[x]/vs[x])
    *S, = [(vs[i], ws[i], ms[i]) for i in I]

    ans = 0
    def greedy():
        yield 0
        for i in range(V + 1):
            if dp[i] > W:
                continue
            rest = W - dp[i]
            r = i
            for v, w, m in S:
                m = min(m, rest // w)
                r += m * v
                rest -= m * w
            yield r
    write("%d\n" % max(greedy()))
solve()

Submission status: Accepted

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

from heapq import heappush, heappop


def max_value(t, xs):
    def _cost(weight, value, i):
        for j in range(i, n):
            v, w = xs[j]
            if weight + w > t:
                return (-value, -value - (v/w)*(t-weight))
            weight += w
            value += v
        return (-value, -value*1.0)

    n = len(xs)
    xs.sort(key=lambda x: x[1], reverse=True)
    xs.sort(key=lambda x: x[0]/x[1], reverse=True)
    u, c = _cost(0, 0, 0)
    heap = [(c, u, 0, 0, 0)]
    maxcost = u
    while heap:
        cost, upper, weight, value, i = heappop(heap)
        if cost > maxcost:
            break
        if i < n:
            v, w = xs[i]
            if weight+w <= t:
                heappush(heap, (cost, upper, weight+w, value+v, i+1))
            u, c = _cost(weight, value, i+1)
            if c < maxcost:
                if u < maxcost:
                    maxcost = u
                heappush(heap, (c, u, weight, value, i+1))

    return -maxcost


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

    for _ in range(n):
        v, w, m = [int(i) for i in input().split()]
        for i in range(m.bit_length()-1):
            h = 2**i
            m -= h
            xs.append((v*h, w*h))
        if m > 0:
            xs.append((v*m, w*m))

    print(max_value(t, xs))


if __name__ == '__main__':
    run()