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
Post a Comment