1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include <map>
using namespace std;
//以best(i, x)表示已经决定了前i件物品是否选取，当前已经选取的物品的所需奖券数总和不超过x时，能够获取的最高的喜好值的和
int Knapsack(vector<int> need, vector<int> values, int ticket)
{
    /* 已经默认best[0][j]=0, 奖品标号是1-N*/
    vector< vector<int> > best(need.size(),vector<int>(ticket+1));
    for (int i=1; i< need.size(); i++)
    {
        for (int j=0; j<=ticket; j++)
        {
            /*如果选择第N件奖品，当然首先要保证第N件商品所需的奖券数不超过M*/
            if( j < need[i] ) best[i][j]=best[i-1][j];
            else
            {
                best[i][j]=max( best[i-1][j], best[i-1][j-need[i]]+values[i] );
            }
        }
    }
    return best[need.size()-1][ticket];
}
/*节省空间*/
int Knapsack2(vector<int> need, vector<int> values, int ticket)
{
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX