Help: Modified Knapsack

Revision en2, by thequacker, 2024-08-23 09:52:21

Problem Link(might not work)

Problem Statement URL

My solution which gives MLE on tc 11


int n, W; cin >> n >> W; vi w(n + 1), v(n + 1); for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; vvi dp(n + 1, vi(W + 1, 0)); for (int i = n; i >= 1; i--) { for (int weight = 0; weight <= W; weight++) { int exclude = 0; if (i + i <= n) exclude = dp[i + i][weight]; int include = 0; if (w[i] <= weight) { include = v[i]; for (int jump = i; i + jump <= n; jump += i) { if (weight >= w[i]) { include = max(include, v[i] + dp[i + jump][weight - w[i]]); } } } dp[i][weight] = max(include, exclude); } } int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, dp[i][W]); } cout << ans << "\n";

How to solve it? ;)

image added if the link is not accesible(wrong spelling nvm)

Problem Statement URL

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English thequacker 2024-08-23 09:52:21 306 Tiny change: 'nvm)\n\n\n![Problem S' -> 'nvm)\n\n\n[Problem S'
en1 English thequacker 2024-08-23 09:24:27 1151 Initial revision (published)