Submission #52670320

---

Source Code Expand

#include <bits/stdc++.h> 
using namespace std;  

typedef long long ll;  
typedef pair<int, int> ii;  

template<typename T>
bool maximize(T& a, const T& b) {
	if (b < a) return false; 
	a = b; 
	return true; 
}

const int INF = 1e9;  
const ll LINF = 1e18;  

// dp knapsack 
// Bài toán gốc: 
// Cho n đồ vật và một balo có khối lượng là S, mỗi đồ vật là có 2 tham số là:   
// w(i): khối lượng của vật thứ i   
// v(i): giá trị của vật thứ i   
// Yêu cầu chọn ra một số món vật sao cho tổng khối lượng w(i) không vượt quá S và tổng giá trị v(i) là lớn nhất?

const int N = 1e2 + 5; 
const int S = 1e5 + 5;    

int n, s;  
int w[N], v[N];  
ll ans;   

void backtrack(int i, ll sum_w, ll sum_v) { // O(2^n)
	if (i == n + 1) {
		ans = max(ans, sum_v);  
		return; 
	}

	// không chọn món vật thứ i   
	backtrack(i + 1, sum_w, sum_v);  

	// chọn món vật thứ i 
	if (sum_w + w[i] <= S) {
		backtrack(i + 1, sum_w + w[i], sum_v + v[i]); 
	}
}

ll dp[2][S]; // dp[i][j] = tổng giá trị v(i) lớn nhất
  			  // 		   khi xét i món vật đầu tiên, tổng khối lượng w(i) của các món vật đã chọn là j 

ll memo[N][S]; 

ll f(int i, int j) {
	if (i == 0) return 0;   

	ll& ans = memo[i][j];   
	if (ans != -1) return ans;   

	// không chọn món vật thứ i
	ans = -LINF;   
	maximize(ans, f(i - 1, j));  

	// chọn món vật thứ i 
	if (j - w[i] >= 0) maximize(ans, f(i - 1, j - w[i]) + v[i]); 

	return ans; 
}	

int main() {
	ios::sync_with_stdio(0); cin.tie(0);  	
	cin >> n >> s;  
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i]; 
	} 

	// ans = -LINF;  
	// backtrack(1, 0, 0); 
	// cout << ans << '\n'; 

	for (int j = 0; j <= s; j++) dp[0][j] = -LINF;  

	dp[0][0] = 0;   
	// O(n * S)
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= s; j++) dp[i % 2][j] = -LINF;  
		dp[i % 2][0] = 0;   
			
		for (int j = 0; j <= s; j++) {
			dp[i % 2][j] = dp[(i - 1) % 2][j]; 
			if (j - w[i] >= 0) maximize(dp[i % 2][j], dp[(i - 1) % 2][j - w[i]] + v[i]); 
		}

	}

	ll ans = 0;   
	for (int j = 0; j <= s; j++) {
		maximize(ans, dp[n % 2][j]); 
	}

	cout << ans << '\n'; 

	// memset(memo, -1, sizeof memo);   

	// ll ans = 0;  
	// for (int j = 0; j <= s; j++) maximize(ans, f(n, j)); 

	// cout << ans << '\n'; 
}

Submission Info

Judge Result