Not able to understand, how does this approach work in solving 0/1 knapsack?

Правка en1, от lazyneuron, 2018-06-21 10:09:54

include<bits/stdc++.h>

using namespace std; int knapsack(int* weights, int* values, int n, int maxWeight){ ios_base :: sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int i, j; int dp[maxWeight + 1]; memset(dp, 0, sizeof dp); int flag = 1; for(i = 1; i <= n; i++) { for(j = maxWeight; j >= weights[i — 1]; j--) dp[j] = max(dp[j], values[i — 1] + dp[j — weights[i — 1]]); } int ans = dp[maxWeight]; return ans; }

Теги #dp, knapsack, arrays, memoization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский lazyneuron 2018-06-21 10:11:59 35
en2 Английский lazyneuron 2018-06-21 10:10:50 132
en1 Английский lazyneuron 2018-06-21 10:09:54 567 Initial revision (published)