Sicily 1782. Knapsack

快来打我* 2022-08-08 00:52 3阅读 0赞

Description

John wants to carry several items with a knapsack. Each item has integral size and can not be divided into smaller parts. The knapsack also has an integral capacity. Given  *n* items, what’s the maximal size of items can be carried without exceeding the knapsack‘s capacity?

Input

This problem contains several test cases. The first line of the input is an integer  *T*, which means there’re  *T* test cases follow. (0 <  *T* ≤ 20)  
Each test case contains two lines. The first line contains two integers  *n*,  *m*, which means that there’re  *n* items totally, and the capacity of the knapsack is  *m*. The second line contains  *n* positive integers, the sizes (smaller than m) of different items. (0 <  *n* ≤ 1000, 0 <  *m*≤ 10000)

Output

For each test case, output one line containing the answer desired.

Sample Input

![Image 1][] Copy sample input to clipboard

2
    3 10
    2 4 7
    5 100
    2 12 81 63 23

Sample Output

9
    100

// Problem#: 1782
    // Submission#: 3708218
    // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
    // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
    // All Copyright reserved by Informatic Lab of Sun Yat-sen University
    #include<iostream>
    #include<cstdio>
    #include<cctype>
    #include<iomanip>
    #include<vector>
    #include<cstring>
    #include<string>
    #include<fstream>
    #include<stack>
    #include<vector>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int size[1000] = {0};
    int maxValue[10000] = {0}; 
    int max(const int& a, const int b){
        return a>b?a:b; 
    }
    int main(){
        int t;   
        cin>>t;    
        while(t--){
            int n,m;                      
            cin>>n>>m;
            for(int k = 0; k < n; k++){
                cin>>size[k];
            }
            for(int i = 1; i <= n; i++){
                for(int j = m; j >= size[i-1]; j--){
                    maxValue[j] = max(maxValue[j],maxValue[j-size[i-1]]+size[i-1]);    
                }
            }
            cout<<maxValue[m]<<endl;
        } 
        return 0;
    }

[Image 1]: