二维背包

Description

给出一个背包，背包有体积容量C和重量限制L，再给出N个物品，每个物品有体积V_i，重量W_i，价值P_i三个参数。每个物品有且仅有一件，求用背包装物品，能获得的最大总价值是多少。

Input

文件的第一行一个数T，表示测试用例子数。接下来T个测试用例。

每个测试用例第一行三个数，N，C，L （0 < N, C, L < 1000）。

接下来N行，每行三个数V_i，W_i，P_i（V_i < 1.5×C, W_i < 1.5×L, P_i < 1000）分别表示物品的体积，重量，价值三个属性。

Output

为每个测试用例输出一行结果：所装物品价值的最大值。

Sample Input

背包模型？1
3 5 5
2 3 1
3 2 1
3 3 3

Sample Output

3

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define NUM 1002
#define INF -66536
int v[NUM],w[NUM],p[NUM]; //分别表示物品的体积，重量，价值三个属性。
int f[NUM][NUM]; //f[v][w]
int N,C,L;//N个物品，背包C体积容量，L重量
int knapsack(){memset(f,0,sizeof(f));for(int i=0;i<N;i++){ //物品的种类for(int j=C;j>=v[i];j--){ //物品的体积for(int k=L;k>=w[i];k--) //物品的质量f[j][k]=max(f[j-v[i]][k-w[i]]+p[i],f[j][k]);}}return f[C][L];
}
int main()
{int T; //测试用例cin >> T;for(int i=1;i<=T;i++){cin >> N >> C >> L;for(int i=0; i<N; i++){cin >> v[i] >> w[i] >> p[i];}cout << knapsack()<<endl;}return 0;
}