algorithm - Variation on knapsack - minimum total cost with exact weight -


there types of items (n types), each have weight wi , cost ci. there infinite number of each. problem make knapsack exact (w) weight , minimum total cost of items. know should use dynamic in case, it's not usual knapsack problem , can't find relation. found similar questions, haven`t understood theese solutions. here links 1, 2. how use dp solve it?

let f[i] means, weight i, minimum cost. g[i] means whether possible combine weight i;

f[0]=0;g[0]=true; (int i=0;i<n;i++)     (int j=0;j<w;j++)         if (g[j]) {             g[j+w[i]]=true;             if (f[j+w[i]]==0||f[j+w[i]]>f[j]+c[i])                 f[j+w[i]]=f[j]+c[i];         }  if (g[w]) return f[w]; else return 0;//impossible 

Comments

Popular posts from this blog

SVG stroke-linecap doesn't work for circles in Firefox? -

routes - Laravel 4 Wildcard Routing to Different Controllers -

cross browser - XSLT namespace-alias Not Working in Firefox or Chrome -