"""Authored 0/1 knapsack table, traceback and wrong in-place ascending loop."""
import itertools,json
from fractions import Fraction

def solve(items,capacity):
    if type(capacity)is not int or not 0<=capacity<=100:raise ValueError('small nonnegative integer capacity')
    if len(items)>12 or any(type(w)is not int or w<=0 or type(v)is not int or v<0 for w,v in items):raise ValueError('positive integer sizes, nonnegative integer values')
    n=len(items);dp=[[0]*(capacity+1) for _ in range(n+1)]
    for i,(w,v) in enumerate(items,1):
        for c in range(capacity+1):
            dp[i][c]=dp[i-1][c]
            if w<=c:dp[i][c]=max(dp[i][c],v+dp[i-1][c-w])
    chosen=[];c=capacity
    for i in range(n,0,-1):
        # Ties keep the exclusion branch, as in the table above.
        if dp[i][c]>dp[i-1][c]:chosen.append(i-1);c-=items[i-1][0]
    chosen.reverse()
    assert len(chosen)==len(set(chosen)) and sum(items[i][0] for i in chosen)<=capacity
    assert sum(items[i][1] for i in chosen)==dp[n][capacity]
    return {'value':dp[n][capacity],'chosen_zero_based':chosen,'total_size':sum(items[i][0] for i in chosen),'table_rows_items_columns_capacity':dp}

def demo():
    items=[(2,5),(3,7),(4,9)];cap=7;r=solve(items,cap);all_subsets=[]
    for flags in itertools.product([0,1],repeat=3):
        picked=[i for i,b in enumerate(flags)if b];w=sum(items[i][0] for i in picked);v=sum(items[i][1] for i in picked)
        all_subsets.append({'items':picked,'size':w,'value':v,'feasible':w<=cap})
    assert r['value']==16 and r['chosen_zero_based']==[1,2] and r['total_size']==7
    assert r['value']==max(x['value'] for x in all_subsets if x['feasible'])
    left=cap;greedy=[]
    for i in sorted(range(3),key=lambda j:(-Fraction(items[j][1],items[j][0]),j)):
        if items[i][0]<=left:greedy.append(i);left-=items[i][0]
    assert greedy==[0,1] and sum(items[i][1]for i in greedy)==12
    ascending=[0]*5;descending=[0]*5
    for c in range(2,5):ascending[c]=max(ascending[c],5+ascending[c-2])
    for c in range(4,1,-1):descending[c]=max(descending[c],5+descending[c-2])
    assert ascending[4]==10 and descending[4]==solve([(2,5)],4)['value']==5
    assert solve(items,0)['value']==0 and solve([],7)['chosen_zero_based']==[]
    invalid=[]
    for bad,capbad in [([(0,1)],2),([(2,-1)],2),([(2,5)],1.5)]:
        try:solve(bad,capbad)
        except ValueError:invalid.append(True)
        else:raise AssertionError('invalid accepted')
    return {'authored_items_size_value':items,'capacity':cap,'table_solution':r,'independent_eight_subsets':all_subsets,'ratio_greedy':{'items':greedy,'value':12,'unused_capacity':left},'one_item_repeat_bug':{'size':2,'value':5,'capacity':4,'ascending_wrong':ascending,'descending_correct':descending},'three_invalid_cases_rejected':invalid,'real_budget_or_customer_data':False}

if __name__=='__main__':print(json.dumps(demo(),indent=2))