题目意思理解

选道具，每个道具可以看成价值为a[i]，重量为c[i]，k是背包容量求最大可选价值，每个道具只能买一次。

切入点与矛盾点

这里c[i],k的范围特别大，不能用普通的办法存储。但是我们可以轻易看出，a[i]的范围很小，1<=a[i]<=500.
所以可以用价值作为dp的下标。
在过程中记录一下有效答案即可。

有注释的代码

#include<bits/stdc++.h>
using namespace std;
int n;
long long k;
int v[505],w[505];
long long dp[250005];//范围大，因为所有道具的价值最大是250000
int main(){
    memset(dp,0x7f,sizeof dp);
    dp[0]=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=250000;j>=v[i];j--){
            dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
            if(dp[j]<=k){//只有重量和不大于背包容量，才可以记录答案
                ans=max(ans,j);
            }
        }
    }
    cout<<ans;
    return 0;
}