BCCAITUI.cpp

/*
Trong siêu thị có n gói hàng (n ≤ 100), gói hàng thứ i có trọng lượng là W i ≤ 100 và trị giá V i
≤ 100. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được
tối đa trọng lượng M ( M ≤ 100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá
trị lớn nhất.
 
INPUT:
5 11
3 3
4 4
5 4
9 10
4 4
 
OUTPUT: // in ra gia tri lon nhat  
11  
*/
 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> ii;
 
int n;
int m;
vector<ii> a;
vector< vector<int> > f;    //luu gia tri toi uu
// f[i][j] i: goi thu i - j: khoi luong
 
void init(){
    cin >> n >> m;
    a.resize(n+1);
    for(int i=1;i<=n;i++) cin >> a[i].first >> a[i].second; // first = WEIGHT, second = VALUE;
    f.resize(n+1, vector<int> (m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j] = f[i-1][j]; // gia su khong chon goi thu i;
            if (j - a[i].first >= 0)    // gia su chon goi thu i va khoi luong con lai > khoi luong goi thu i;
                f[i][j] = max(f[i][j], f[i-1][j-a[i].first] + a[i].second); // cap nhat f[i][j]; 
            // cout << f[i][j] << endl;
        }
    }
    // cout << "Khoi luong lon nhat: ";
    cout << f[n][m] << endl;
}
 
void process(){
 
 
}
 
int main(){
 
    init();
    process();
 
    return 0;
}