题解：P11377 [GESP202412 七级] 武器购买

· · 题解

本题是典型 01 背包问题（属于动态规划）。动态规划分三步走。

STEP 1（状态表示）：

输出的答案应为 f_0 至 f_Q 第一个大于等于 P 的 i，所以 f_W=V 其中 W 为花费， V 武器的最大强度。

STEP 2（状态转移方程）：

当选择 a_i ，会减少 c_i 的花费，增加 p_i 的强度，但注意，要与以前的状态进行对比。不然就不是最优解。

STEP 3（初始化）：

显然，对于任意 f_i 初始值都是 1。

CODE：

#include<bits/stdc++.h>
#define AK return
#define IOI 0
using namespace std;

int T,n,P,Q;
int minn;

struct ths{//结构体对缓存更友好
    int w;
    int v;
};

ths a[1500];
int f[100050];

int main(){
    scanf("%d",&T);
    while(T--){//T组数据
        //输入
        scanf("%d%d%d",&n,&P,&Q);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i].v,&a[i].w);
        }
        memset(f,0,sizeof(f));//有多组数据，应memset
        for(int i=1;i<=n;i++){//物品
            for(int j=Q;j>=a[i].w;j--){//背包
                f[j]=max(f[j],f[j-a[i].w]+a[i].v);
            }
        }
        //取最小i
        minn=-1;
        for(int i=0;i<=Q;i++){
            if(f[i]>=P){
                minn=i;
                break;
            }
        }
        cout<<minn<<endl;//输出
    }
    AK IOI;
}