The first line contains the integer ? indicating to the number of test cases.
For each test case, the first line contains the integers ? and ?.
Following ? lines provide the information of each item.
The
?
All the inputs are integers.
1 5 15 12 4 2 2 1 1 4 10 1 2
15
#include <cstdio> #include <iostream> #include <queue> #include <cstring> #include <string> #include <cmath> using namespace std; #define ll long long int t, n, pri, p[500+8], v[500+8], dp[500+8][5000+8], sum; void solve() { fill(dp[0], dp[0] + 5005, 0x3f3f3f3f); dp[0][0] = 0; for(int i = 0; i<n; i++) { for(int j = 0; j <= 5001; j++) { if(j<v[i]) dp[i+1][j] = dp[i][j]; else dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+p[i]); } } int miao = 0; for(int i = 0; i <= 5001; i++) { if(dp[n][i] <= pri) miao = i; } printf("%d\n", miao); } int main() { scanf("%d", &t); memset(dp, 0, sizeof(dp)); memset(p, 0, sizeof(p)); memset(v, 0, sizeof(v)); while(t--) { scanf("%d%d", &n, &pri); for(int i = 0; i<n; i++) { scanf("%d%d", &p[i], &v[i]); } solve(); } return 0; }
SDNU 1539 Do you like Hot Dog ?
原文：https://www.cnblogs.com/RootVount/p/10326113.html