DP.rar_dp算法

#include <stdio.h> #include <stdlib.h> #define iSize 5 int max(int m, int n) { return m > n ? m : n; } int min(int m, int n) { return m > n ? n : m; } void knapsack(int v[], int w[], int c, int *m[], int len) { int n = len - 1; int jMax = min(w[n] - 1, c); int i, j; for (j = 0; j <= jMax; j++) m[n][j] = 0; for (j = w[n]; j <= c; j++) m[n][j] = v[n]; for (i = n - 1; i > 1; i--) { jMax = min(w[i] - 1, c); for (int j = 0; j <= jMax; j++) m[i][j] = m[i+1][j]; for (j = w[i]; j <= c; j++) m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]); } m[1][c] = m[2][c]; if (c >= w[1]) m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1]); } int main() { int v[iSize] = {6, 3, 5, 4, 6}; int w[iSize] = {2, 2, 6, 5, 4}; int c = 10; int **m = new int*[5]; for (int i = 0; i < iSize; i++) m[i] = new int[c]; knapsack(v, w, c, m, iSize); printf("%d\n", m[1][c]); delete m; system("pause"); return 0; }