例题链接:
http://www.acmicpc.sdnu.edu.cn/problem/show/1520
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long ll; ll a[100005]; int main() { int m; cin >> m; while(m--) { memset(a, 0, sizeof(a)); ll t,n; cin >> t >> n; for (ll i=1;i<=n;i++) //个数 { ll x,y,z; cin >> x >> y >> z; //对第i个物品检测次数 = 其现有数目(相当于0-1背包多了几个种类) for (int k=1;k<=z;k++) { for (ll j=t;j>=x;j--) { a[j]=max(a[j],a[j-x]+y); } } } cout << a[t] << endl; } return 0; }