c++采购奖品不知道哪里错了

Question

我的代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long qwe;
int a[99999],b[99999];
int main(){
    int m,n,i,j,q=0;
    cin>>m>>n;
    for(i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    for(i=1;i<n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            if(a[i]>a[j])
            {
                swap(a[i],a[j]);
                swap(b[i],b[j]);
            }
        }
    }
    int som=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=b[i];j++)
        {
            som+=a[i];
            if(som>=m)
                break;
            q++;
        }
        if(som>=m)
            break;
    }
    cout<<q;
    return 0;
}//?筍?

有会的请发下代码

Answer 1

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;

    int a[n], b[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
    }

    int f[m + 1];
    fill(f, f + m + 1, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = a[i]; j <= m; j++)
        {
            f[j] = max(f[j], f[j - a[i]] + b[i]);
        }
    }

    cout << f[m] << endl;

    return 0;
}

这是一道典型的0/1背包问题。

在这道题中，需要用尽可能多的钱来购买尽可能多的物品，且每种物品只有一件，可以用0/1背包的思路来解决。

具体来说，可以用一个数组f[i]来表示用i元钱最多可以购买多少件物品。然后遍历每种物品，如果用j元钱可以购买当前物品，就f[j] = max(f[j], f[j - a[i]] + b[i])，其中a[i]和b[i]分别表示第i种物品的单价和库存数量。

输出f[m]即可。
仅供参考，望采纳，谢谢。