Untitled
unknown
c_cpp
a year ago
865 B
5
Indexable
Never
#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 int main(){ 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; return 0; }