最简单的背包问题了，本题应该除了背包就一个考点了：不能开二维数组。我没开过二维，不过看数据是不可以的。太大了。

做法有两种改进省内存DP：

1 所谓的滚动数组

2 逆向填表

很久没做背包DP，突然觉得这种背包问题很简单了。

下面给出两种解法:

1 calBag()是滚动数组

2 calBag2()是逆向填表

#pragma once
#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int MAX_W = 12881; const int MAX_N = 3403; int N, M;//M是total weight int wei[MAX_N]; int desi[MAX_N]; int tbl[MAX_W]; int calBag2() { memset(tbl, 0, sizeof(int)*(M+1)); for (int i = 1; i <= N; i++) { for (int j = M; j >= wei[i]; j--) tbl[j] = max(tbl[j], tbl[j-wei[i]]+desi[i]); } return tbl[M]; } int calBag() { vector
     
       > tbl(2, vector
      
       (M+1)); bool id = true; for (int i = 1; i <= N; i++) { for (int j = 1; j < wei[i] && j <= M; j++) tbl[id][j] = tbl[!id][j]; for (int j = wei[i]; j <= M; j++) { tbl[id][j] = max(tbl[!id][j], tbl[!id][j-wei[i]]+desi[i]); }//注意都是上一列的数据往下拉,都是!id数列比较 id = !id; } return tbl[!id][M]; } int main() { while (scanf("%d %d", &N, &M) != EOF) { for (int i = 1; i <= N; i++) { scanf("%d %d", &wei[i], &desi[i]); } printf("%d\n", calBag2()); } return 0; }