为界背包DP算法？ [英] DP algorithm for bounded Knapsack?

问题描述

借助约背包问题维基百科的文章，包含了列表三种：

The Wikipedia article about Knapsack problem contains lists three kinds of it:

1. 1-0（一类型的一个项目）

1. 1-0 (one item of a type)

有界（一类型的多个项目）

Bounded (several items of a type)

无界（不限数量的一类项目）

Unbounded (unlimited number of items of a type)

本文包含DP方法为1和3类型的问题，但对于2无解的。

The article contains DP approaches for 1. and 3. types of problem, but no solution for 2.

如何动态规划算法求解2描述？

How can the dynamic programming algorithm for solving 2. be described?

推荐答案

使用0-1变量，但允许一个项目的重复的解决方案达在其绑定中指定的次数。您需要保持一个矢量说明你已经包含在部分解的每个项目的多少份

Use the 0-1 variant, but allow repetition of an item in the solution up to the number of times specified in its bound. You would need to maintain a vector stating how many copies of each item you already included in the partial solution.

这篇关于为界背包DP算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！