传送门

题目描述：

样例输入：

3 24
4 4 4
2 2 2

 样例输出：

18

题意：做 dp 题都需要简化题意，这道题的意思大概就是展示策略达到 mm 种的最小花费。

思路：根据题目要求的量，我们来设计状态。我们看到，方案数量是价值，Q币数量是我们的花费，我们这么来表示状态：dp[j]表示花费j个Q币的最大方案数量。我们得到一维的状态转移方程：

dp[j]=max(dp[j],dp[j-k*v[i]]*k);

代码：

#include<iostream>
using namespace std;
#define ll long long
const ll N=1e7+5;
ll dp[N];
ll w[N],v[N];
ll n,m;
ll sum;int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>w[i];//皮肤个数}for(int i=1;i<=n;i++){cin>>v[i];//皮肤价钱sum+=v[i]*w[i];}dp[0]=1;for(int i=1;i<=n;i++){for(int j=sum;j>=0;j--){for(int k=0;k<=w[i];k++){if(j>=k*v[i]){dp[j]=max(dp[j],dp[j-k*v[i]]*k);}}}}for(int i=1;i<=sum;i++){if(dp[i]>m){cout<<i<<endl;return 0;}}return 0;
}