我实现了2种解决knapsack的方法，但我不能用1种方法打印所选的项目，而另一种方法又不能很好地工作，因为它漏掉了我的第一个项目值。简单来说，我的knapsack问题是将一个长度为N的条形图划分为长度为1,2,......,N的子条形图，每个子条形图的成本不同。
当然，只要你不超过长度，物品的重复是允许的，所以:1)我有一个长度为N的条，可以进行分割。2)用Knapsack找到最大的利润，在这里可以多次取相同的物品.3)打印Knapsack选择的元素。
我的问题是：1)在第一段代码中，我不明白如何打印所选的项目。2)我尝试了矩阵的方法，但我不明白如何设置Knapsack矩阵的方程，允许项目重复。
这是我的第一次尝试，这实际上是有效的，并给了我正确的答案，但我真的不明白如何打印选择的项目。
int *k = malloc(sizeof(int ) * lenght+1);
for( i = 0 ; i <= lenght; i++) k[i] = 0;
填充 knapsack 数组。
for(i = 0 ; i <= lenght ; i++){
for(w = 0 ; w < lenght ; w++){
if( bar[w] <= i){
k[i] = searchmax( prices[w] + k[i-bar[w]] , k[i] );
}
}
}
这是我的第二种方法，它不工作，但我更清楚如何打印项目后，因为它与经典的knapsack工作。
int **k = malloc(sizeof(int*) * (lenght+1));
for(i=0;i<=lenght;i++) k[i] = malloc(sizeof(int)*(lenght+1));
for( i = 0 ; i <= lenght; i++)k[0][i]= 0;
for(i = 0 ; i <=lenght;i++) k[i][0]=0;
for(i=1;i<=lenght;i++){
for(w=1;w<=lenght;w++){
if(bar[i]<=w){
printf("\nPrices: %d Barlenght: %d" , prices[i], bar[i]);
k[i][w]=searchmax(prices[i]+k[i][w-bar[i]], k[i-1][w]);
}
else k[i][w] = k[i-1][w];
}
}
这组输入的结果是 栏的长度： 4
长度为1到N的子条的价格，其中N在本例中是4，是：1，5，8，9。
应该是 。利润：10 ，项目：2 ，2 2 , 2
你应该只打印 "保存在背包中 "的元素。每一次迭代，你都要检查是否将一个元素放入背包中，还是将其丢弃。在你的代码中，你应该检查：如果一个元素 "被保存在背包中"，打印它和它的重量，以及其他已经在背包中的值，当添加这个元素时，不要超过背包的容量。有几种方法可以做到这一点。我想了想：在执行该方法的同时，将knapsack中每个可能的容量（如果它的容量为W，你必须将所选的值存储在一个矩阵中，其中每行w代表一个值0 <= w <= W），列中包含knapsack中具有一定容量的元素。如果你有不明白的地方，请告诉我，我可以解释。
程序代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <string>
/**
* Responsible for dealing with the unbounded knapsack problem.
*/
class UnboundedKnapsack
{
//-------------------------------------------------------------------------
// Attributes
//-------------------------------------------------------------------------
/**
* Stores maximum value of the knapsack for a certain capacity.
*/
std::vector<int> knapsack;
/**
* Stores elements that are part of the knapsack with a certain capacity.
* <li><b>Line:</b> Knapsack capacity</li>
* <li><b>Column:</b> Elements</li>
*/
std::vector<std::vector<int> > selectedElements;
/**
* Stores maximum knapsack capacity.
*/
int maximumCapacity;
public:
//-------------------------------------------------------------------------
// Constructor
//-------------------------------------------------------------------------
UnboundedKnapsack()
{
maximumCapacity = -1;
}
//-------------------------------------------------------------------------
// Destructor
//-------------------------------------------------------------------------
~UnboundedKnapsack()
{
delete this;
}
//-------------------------------------------------------------------------
// Methods
//-------------------------------------------------------------------------
/**
* Unbounded knapsack allows to use one or more occurrences of an item.
*
* @param w Weight of the elements
* @param v Value of the elements
* @param N Number of itens
* @param W Maximum weight capacity
* @return This object to allow chained calls
*/
UnboundedKnapsack* knapsack_unbounded(std::vector<int>& w, std::vector<int>& v, int N, int W)
{
// Stores the maximum value which can be reached with a certain capacity
knapsack.clear();
knapsack.resize(W + 1);
maximumCapacity = W + 1;
// Stores selected elements with a certain capacity
selectedElements.resize(W + 1);
// Initializes maximum value vector with zero
for (int i = 0; i < W + 1; i++) {
knapsack[i] = 0;
}
// Computes the maximum value that can be reached for each capacity
for (int capacity = 0; capacity < W + 1; capacity++) {
// Goes through all the elements
for (int n = 0; n < N; n++) {
if (w[n] <= capacity) {
// max(knapsack[capacity], knapsack[capacity - w[n]] + v[n])
if (knapsack[capacity] <= knapsack[capacity - w[n]] + v[n]) {
knapsack[capacity] = knapsack[capacity - w[n]] + v[n];
// Stores selected elements
selectedElements[capacity].clear();
selectedElements[capacity].push_back(n + 1);
for (int elem : selectedElements[capacity - w[n]]) {
selectedElements[capacity].push_back(elem);
}
}
}
}
}
return this;
}
/**
* Returns maximum value for a certain number of elements and a certain
* capacity.
*
* @param capacity Capacity of the knapsack
* @return Maximum possible value with capacity provided
* @throws std::invalid_argument If capacity provided is out of bounds
*/
int getMaximumValue(int capacity)
{
if (capacity < 0 || capacity >= maximumCapacity)
throw std::invalid_argument("Capacity out of bounds");
return knapsack[capacity];
}
/**
* Returns elements that belong to the knapsack with a certain capacity.
*
* @param capacity Capacity of the knapsack
* @return Elements that are part of the knapsack with the capacity
* provided
* @throws std::invalid_argument If capacity provided is out of bounds
* @apiNote Elements are referenced by their index + 1
*/
std::vector<int>& getSelectedElements(int capacity)
{
if (capacity < 0 || capacity >= maximumCapacity)
throw std::invalid_argument("Capacity out of bounds");
return selectedElements[capacity];
}
/**
* Returns elements that are part of the knapsack with a certain capacity.
* This method will return a {@link std::string} with the following format:
* <code>[elem1, elem2, elem3...]</code>
*
* @param capacity Capacity of the knapsack
* @return Elements that are part of the knapsack with the capacity
* provided
* @apiNote Elements are referenced by their index + 1
*/
std::string selectedElements_toString(int capacity)
{
std::string response = "[";
for (int element : selectedElements[capacity]) {
response.append(std::to_string(element));
response.append(", ");
}
// Removes last ", "
response.pop_back();
response.pop_back();
response.append("]");
return response;
}
};
//-------------------------------------------------------------------------
// Main
//-------------------------------------------------------------------------
/**
* Example made based on this exercise:
* {@link https://www.urionlinejudge.com.br/repository/UOJ_1487_en.html}
*/
int main()
{
UnboundedKnapsack* knapsack = new UnboundedKnapsack();
int totalCapacity = 60, elements = 5;
std::vector<int> elements_weight = { 10, 20, 5, 50, 22 };
std::vector<int> elements_values = { 30, 32, 4, 90, 45 };
knapsack->knapsack_unbounded(elements_weight, elements_values, elements, totalCapacity);
std::cout << "Maximum value: "
<< knapsack->getMaximumValue(totalCapacity)
<< std::endl;
std::cout << "Selected elements: "
<< knapsack->selectedElements_toString(totalCapacity)
<< std::endl;
system("pause");
return 0;
}
产量
Maximum value: 180
Selected elements: [1, 1, 1, 1, 1, 1]
我希望这能帮助你。如果你有兴趣，我还实现了一个版本，可以显示存储在经典版背包中的元素。它可以在这里找到。https:/github.comwilliamniemiecalgorithmsblobmasterDynamic%20programmingknapsackc%2B%2BBoundedKnapsack.cpp