如何获得无界背包问题中使用的物品数量？

Question

我正在尝试解决一个无界背包问题，但我被卡住了。我已经解决了问题的主要部分，即获取最大值，但我还应该计算出我使用了多少个项目才能获得最大答案。
界限是小于 100 件物品和小于 100 背包容量。示例输入是
3（项目数）
8（背包容量）
5 21（分别为重量和价值）
3 1
4 15

输出为
30件（包内可装的最大值，即4件重量中的2件）
0 0 2（背包里每件物品的数量）

我不知道如何打印最后一行输出，我已经被这个问题困了一个星期了。我在别处问过，他们说要存储我以前的状态，但我不确定该怎么做。到目前为止，这是我的代码。感谢任何帮助。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

int wt[101];
int val[101];
int ans[101];
int cnt[101];

int knapsack(int s, int N, int val[], int wt[]){
    
    for(int i=0;i<=s;i++){
        for(int j=0;j<N;j++){
            if(wt[j]<=i){
                int tmp = ans[i];
                ans[i] = max(ans[i], ans[i-wt[j]] + val[j]);
                
            }
        }
    }
    return ans[s];
}
int main() {
    
    int N, s, i, j, k, w, p;
    
    
    scanf("%d", &N);
    scanf("%d", &s);
    for(i=0;i<N;i++){
        scanf("%d %d", &wt[i], &val[i]);
    }
    
    printf("%d\n", knapsack(s, N, val, wt));
    
    
    
    
    return 0;
}

Answer 1

我认为您需要考虑您的基本组织。我不会为你做功课，但我会尝试给出一些提示。

你对背包问题的解释似乎有问题。让我确保我们遇到了同样的问题。

你有一个 knapsack（背包）。它最多可以承受 N“磅”。

你有好几堆东西可以放进背包。每个都有一个权重和一个值。

想法是弄清楚如何将价值最高的背包塞进去。

换个角度想很有意思。想象一下，您在商店里赢得了一次疯狂购物。您需要装满购物车，并且希望获得最大的价值。因此，您会选择最昂贵的商品并尽可能地装满购物车，但当您快完成时，您会选择较小的商品并塞满角落。

最后，你需要知道：

-购物车中物品的总价值是多少 -里面到底有什么

这实际上是一个棘手的问题。我将从这个开始：我的数据结构。我会使用 class 来保存可能的项目：

class Item {
public:
     int weight;
     int value;
};

听起来你不必担心容器 classes (std::vector)，所以让我们做一个数组：

Item items[100];

您拥有的用于读取输入的代码大部分都不错，但是您可以执行以下操作，而不是读取您的各个数组：

for(index = 0; i < N; index++){
    Item & item = items[index];
    scanf("%d %d", &item.weight, &item.value);
}

现在您的项目数据存储在一起，这有助于考虑您的项目。

我要谈谈一些文体方面的事情。首先，我不喜欢你的变量名。最好避免缩写。你会看到我把它们拼出来了。此外，单个字母的变量名很难搜索。你会看到我使用索引而不是我。您的代码中将有一百万个 i 实例，但没有那么多 index 实例。

另一种使代码更易于阅读的风格：空格。我们负担得起。我不喜欢看到所有东西都被挤在一起，因为我认为这会让阅读变得更加困难。不要害怕空格。

显然，这两段是一种观点，因此请按其价值接受它。

此时，你必须解决问题。你如何最优化地装满背包/手推车/背包。

你学会递归了吗？想想这段代码。

想象一个名为 findSolution 的方法。您将递归调用它，尽管您也可以在双嵌套循环中执行此操作。

该方法决定“如果我们不使用任何第一项，我们就是最好的。使用其余项目的最佳解决方案是什么？”它调用自己，但说要跳过第一项。

然后它说，“如果我把第一个项目中的一个放进去呢？”然后在剩下的列表中调用自己。

当它返回时，我看到，“哦，与我不使用任何东西相比，将 1 放入给我的总价值更高，所以这是我暂定的最佳解决方案。”

你循环检查，直到你用完第一个项目的所有 8 个插槽，找出最好的。

编码很棘手，可能需要一点时间，但这是解决这个问题的一种方法。将结果存储在另一个 class 中，然后打印它很容易。

如何获得无界背包问题中使用的物品数量？

How to get the number of items used in an unbounded knapsack problem?

c++

knapsack-problem