Problem description

Yes N Items and a volume of M Backpack . The first i Volume of items
w[i], Value is d[i]. Find out which items to pack into the backpack to make the total value
And maximum . There is only one item of each kind , You can choose to put it or not
(N<=3500,M <= 13000

thinking

use F[i][j] Pre fetching i Species , So that their total volume does not exceed j Optimality
Total value obtained by taking method . Requirement F[N][M]
boundary ：if (w <= j)
F[j] = d;
else
F[j] = 0;

Recurrence ： F[i][j] = max(F[i-1][j],F[i-1][j-w[i]]+d[i])
Take or not i Species , The two are selected.
(j-w[i] >= 0 There's a second )

This topic is like memory recursion , A large two-dimensional array is needed , Meeting
Super memory . Notice the value of the next row of this two-dimensional array , It's only used.
Values directly above and to the left of the previous line , So we can use the idea of rolling array
, Just one line . One dimensional array can be used , use “ Everyone for me ”
Recursive dynamic reduction implementation

Central code
int knapSack(int w[],int v[],int C) { int size = w.length; if (size == 0) {
return 0; } int dp[][] = new int[size][C + 1]; // Initialize first line // Only capacity is considered C My backpack 0 Items
for (int i = 0; i <= C; i++) { dp[i] = w <= i ? v : 0; } // Fill in other rows and columns for
(int i = 1; i < size; i++) { for (int j = 0; j <= C; j++) { dp[i][j] = dp[i - 1]
[j]; if (w[i] <= j) { dp[i][j] = max(dp[i][j], v[i] + dp[i - 1][j - w[i]]); } }
} return dp[size - 1][C]; }

Technology
Daily Recommendation
views 26