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

android - Why am I getting the message 'Youractivity.java is not an activity subclass or alias' -

Making Empty C++ Project: General exception (Exception from HRESULT:0x80131500) Visual Studio Community 2015 -

How to fix java warning for "The value of the local variable is not used " -