如何得到一个无界背包问题中使用的物品数？

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

我想你需要考虑一下你的基本组织。我不打算替你做作业，但我会试着给你一些提示。

你对背包问题的解释似乎有缺陷。让我确定我们有同样的问题。

你有一个背包（背包）。它最多可以容纳N“磅”。

如果你换一种想法，那就很有趣了。想象一下你在商店里赢得了一场购物狂欢。你可以装满购物车，你想尽可能地利用最大的价值。所以你去买最贵的东西，尽可能地把手推车装满，但当你快买完的时候，你就去买小东西，把角落塞满。

最后，你需要知道：

-手推车里的东西的总价值是多少-实际上是什么

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

Item items[100];

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

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

另一个使代码更容易阅读的风格上的东西：空格。我们买得起。我不喜欢看到东西被塞在一起，因为我认为这会让阅读变得更加困难。不要害怕空间。

很明显，这两段是一种观点，所以要考虑它的价值。

当它回来时，is看到，“哦，加1比不加1会给我一个更好的总价值，所以这是我暂定的最佳解决方案。”

您循环检查，直到您使用了所有8个插槽，只有第一个项目，找出什么是最好的。

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