学步园

小记： 这题一看 就是dp，但是出题的时候 一同学说都是搜索题，刚开始我用一维dp，发现不行，因为有两个约束条件，我就将dp删了，用dfs做，就情况来说，想的头痛，然后认真分析，这是一个典型的0/1背包，只不过要用个二维数组，约束两个条件，于是一个三重循环，直接AC了。

思路：dp，三重循环，第一重枚举石头，第二重枚举重量，第三重枚举石头个数，因为每种石头只有一个，所以重量和石头个数都是从大到小枚举。背包问题，详情请看背包九讲，我的blog里也有一篇讲解的，点击这里

状态转移方程：dp[w][k] = max(dp[w][k],dp[w - f[i].w][k-1] + f[i].value)

dp数组初始化 为0

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_ = 1001;

struct point{
    int w,v;
} f[MAX_];
int dp[MAX_][MAX_];
int weight, n , k;

int main() {
    int T;
    cin>>T;
    while(T--) {
        cin>>n>>k;
        for(int i = 1; i <= n; ++i){
            cin>>f[i].v>>f[i].w;
        }
        cin>>weight;
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n; ++i){
            for(int j = weight; j > -1; --j){
                for(int r = k ; r > -1; --r){
                    if(j >= f[i].w && r > 0){
                        dp[j][r] = max(dp[j][r],dp[j - f[i].w][r - 1] + f[i].v);
                    }
                }
            }
        }
        cout<<dp[weight][k]<<endl;

    }
    return 0;
}