背包问题（如何定义dp状态）

前言：我们要如何定义dp的定义呢，我们不能像正常那样，定义为花费了 i 钱得到的最大收益，我们这一题需要的是收益为 i 的时候的最小花费，那么我们就需要定义为达到收益为 v 的时候的最小花费

这一题有一个难点就是，我们收益大于当前的 i 值的时候，也要当作 i 进行转移

#include<bits/stdc++.h>
using namespace std;#define int long long
const int N = (int)1e3+10;
int b[N],c[N];
int n,m,v;
vector<int> sto[N];bool cmp(int a,int b){return a>b;
}
// 考虑用
signed main(){cin>> n >> m >> v;for(int i=0;i<n;i++){cin >> b[i] >> c[i];}for(int i=1;i<=m;i++){int a,t;cin >> a >> t;sto[t].push_back(a);}// 从大到小排序for(int i=0;i<n;i++){sort(sto[i].begin(),sto[i].end(),cmp);}vector<int> bag(v+10,0x3f3f3f3f);bag[0] = 0;for(int i=0;i<n;i++){if(sto[i].size()==0) continue;for(int j=v;j;j--){int now = 0; int cost = b[i];for(int k=0;k<sto[i].size();k++){now += sto[i][k]; cost += c[i];int d = now - cost;if(d<=0) break;d = min(d,j);bag[j] = min(bag[j],bag[j-d]+cost);}}}cout << bag[v];system("pause");return 0;
}