用动态规划法设计算法有一根长n厘米的金属棒,现在要切割成几段零售.i 厘米(i = 1,2,...,n)长的金属棒零售价

1个回答

  • 这个题目可以看作是个完全背包问题的变形.

    转化成一个体积为n的背包,向里面放东西,使得所有东西体积之和恰好为n(正统的背包问题是不大于n),而且总的价值最大.其中每件编号为i的东西体积为c[i](长度),价格为w[i](零售价).

    这个问题非常类似于01背包问题,所不同的是每种物品有无限件.也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种.如果仍然按照解01背包时的思路,令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值.仍然可以按照每种物品不同的策略写出状态转移方程,像这样:f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i] (其中0