背包以最小的成本 [英] Knapsack with minimum cost

问题描述

我有几种类型的硬币，每个人都有重量（WI）和成本（CI）。所以，我不得不做出一个背包与体重= W和它硬币（！）的最低成本。我不能老是让递推关系使用DP。

I've got several types of coins, each have weight (wi) and cost (ci). So I've got to make a knapsack with weight==W and (!) minimum cost of coins in it. I can`t make recurrence relation to use DP.

推荐答案

刚刚制定通常递推关系......

Just formulate the usual recurrence relation...

指定最小成本达到的总权重k作为Min_cost（k）的

Designate the minimum cost achievable with total weight k as Min_cost(k).

自引导与记忆化：

Min_cost(0) = cost of empty set = 0

然后解决增加使用的k值：

Then solve for increasing values of k using:

Min_cost(i+1) = min [Min_cost(i)   + min [ci, for all items with wi = 1],
                     Min_cost(i-1) + min [ci, for all items with wi = 2],
                     Min_cost(i-2) + min [ci, for all items with wi = 3],
                     ...
                     Min_cost(2) + min [ci, for all items with wi = w-1],
                     Min_cost(1) + min [ci, for all items with wi = w],
                     Min_cost(0) + min [ci, for all items with wi = w+1]]

这篇关于背包以最小的成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！