在我的背包实施中遇到问题（PARTY）

Question

我今天想从 spoj 做 this simple question，它是背包问题，我已经实现如下：

#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实现精确解，而是贪心算法，一般不会计算出最优解。然而，问题中 link 的任务显然需要生成最佳解决方案。

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

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

贪婪算法会选择 Item 1，产生 6 的利润。然而，选择 Item2 和 Item3 会产生 7.

的总利润

在我的背包实施中遇到问题（PARTY）

Getting problems in my knapsack implementation(PARTY)

c++

algorithm

dynamic-programming

knapsack-problem