Minimum cost to fill given weight in a bag | Python3 program to find minimum cost to get exactly W Kg with given packets ; Returns the best obtainable price for a rod of length n and price [ ] as prices of different pieces ; Build the table val [ ] in bottom up manner and return the last entry from the table ; Driver code
import sys NEW_LINE def minCost ( cost , n ) : NEW_LINE INDENT dp = [ 0 for i in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT min_cost = sys . maxsize NEW_LINE for j in range ( i ) : NEW_LINE INDENT if j < len ( cost ) and cost [ j ] != - 1 : NEW_LINE INDENT min_cost = min ( min_cost , cost [ j ] + dp [ i - j - 1 ] ) NEW_LINE DEDENT DEDENT dp [ i ] = min_cost NEW_LINE DEDENT return dp [ n ] NEW_LINE DEDENT cost = [ 10 , - 1 , - 1 , - 1 , - 1 ] NEW_LINE W = len ( cost ) NEW_LINE print ( minCost ( cost , W ) ) NEW_LINE