c++ - 在我的背包实现中遇到问题(PARTY)

Question

我正在尝试做 this simple question今天从 spoj 开始，它是背包问题，我已经实现如下:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    while(true)
    {
        int budget, t;
        scanf("%d%d", &budget, &t);
        if(budget == 0 && t == 0)
            break;

        int cost[t], fun[t]; 
        vector<pair<double, int> > knap;
        for(int i = 0;i < t;i++)
        {
            scanf("%d%d", &cost[i], &fun[i]);
            knap.push_back(pair<double, int>(double(fun[i])/double(cost[i]), i));        
        }
        sort(knap.rbegin(), knap.rend());
        int totfun = 0, bud = budget;
        for(int i = 0;i < int(knap.size());i++)
        {
            if(bud - cost[knap[i].second] >= 0)
            {
                bud -= cost[knap[i].second];
                totfun += fun[knap[i].second];        
            }
        }
        printf("%d %d\n", budget-bud, totfun);
    }
}

但是这个解决方案给出了 WA(错误答案)。我已经尝试了spoj自己的论坛中的所有测试用例，我的代码似乎都通过了，谁能指导我，这是我尝试过的第一个DP问题......

Answer 1

问题中的代码没有通过Dynamic Programming实现精确解，而是一种贪心算法，通常不会计算出最优解。但是，问题中链接的任务显然需要生成最佳解决方案。

贪婪算法的次优性可以通过考虑以下实例来证明。

Item 1: Function 6, Cost 4 (Ratio 18/12)
Item 2: Function 4, Cost 3 (Ratio 16/12)
Item 3: Function 3, Cost 3 (Ratio 12/12)

Capacity: 6

贪心算法会选择项目 1，产生 6 的利润。但是，选择 Item2 和 Item3 会产生 7 的总利润。