• 题目描述：

输入格式是第一行一个正整数N（1< =N< =100）表示总共的娱乐项目数；第二行一个正整数表示规定的时间t（0< t< 1000）；下面有N行，其中第i+2行有两个正整数fi（0< =fi< =100）和ti（0< ti< =100），分别表示对项目i的“喜欢度”和它所耗费的时间。输出的时候在第一行输出最大的“喜欢度”之和，下面给你一个样例：

• 输入：

3
5
1 2
5 5
4 3

• 输出：

5

• 总结：
  • 这是典型的01背包问题，不是贪心算法可以解决的

include
#include
#define Max(N1,N2) N1>N2?N1:N2
using namespace std;
int main()
{
int N, T, max=0;
vector value, cost;
vector dp;
cost.push_back(0);
value.push_back(0);
cin>>N>>T;
//scanf(“%d%d”, &N, &T);
for (int i = 1; i <= N; i++)
{
int v,c;
cin >> v >> c;
//scanf(“%d%d”, &v, &c);
value.push_back(v);
cost.push_back(c);
}

//这是01背包问题的优化算法
dp = vector(T+1, 0);
for (int i = 1; i <= N; i++)
{
for (int j = T; j >= cost[i]; j—)
{
dp[j] = Max(dp[j], dp[j - cost[i]] + value[i]);
}
}

max = dp[T];
printf(“%d\n”, max);
return 0;
}