从零到一掌握背包问题：洛谷P1164题解精讲，附带优化

19339201706

题目重解：

小A带着m元钱来到餐馆，菜单上有n道菜，每道菜都有确定的价格。现在需要计算出刚好花完m元的点菜方案总数。这个问题看似简单，但当菜品数量增多时，暴力枚举就会变得不可行，需要更高效的算法来解决。

解题思路：

动态规划方法解决这个问题。首先定义一个二维数组dp，其中dp[j]表示前i道菜花费j元的方案数。初始化时，dp[0][0]为1（0道菜花0元有1种方案）。然后通过双重循环遍历每道菜和每个可能的金额：

1.当当前菜品价格大于当前金额时，直接继承前i-1道菜的结果

2.当金额正好等于菜品价格时，方案数增加1（单独点这道菜）

3.当金额大于菜品价格时，方案数为不选这道菜的方案数加上选了这道菜后剩余金额的方案数之和 最终dp[n][m]就存储了恰好花完m元的方案总数。

代码+注释：

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. int main()
   
5. {
   
6.     int n,m;  // n是菜品数量，m是总金额
   
7.     cin>>n>>m;
   
8.     int* a=new int[n];  // 存储每道菜的价格
   
9.     for(int i=0;i<n;i++)
   
10.         cin>>a[i];
    
11.    
    
12.     // 初始化动态规划数组
    
13.     int** dp=new int*[n+1];
    
14.     for(int i=0;i<=n;i++){
    
15.         dp[i]=new int[m+1];
    
16.         for(int j=0;j<=m;j++) dp[i][j]=0; // 初始化为0
    
17.     }
    
18.     dp[0][0]=1;  // 基础情况：0道菜花0元有1种方案
    
19. 
    
20.     // 动态规划过程
    
21.     for(int i=1;i<=n;i++){
    
22.         for(int j=1;j<=m;j++){
    
23.             if(j<a[i-1]) dp[i][j]=dp[i-1][j];  // 当前菜太贵，无法选择
    
24.             else if(j==a[i-1]) dp[i][j]=dp[i-1][j]+1;  // 刚好可以单独点这道菜
    
25.             else dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i-1]];  // 不选或选这道菜两种情况之和
    
26.         }
    
27.     }
    
28.     cout<<dp[n][m];  // 输出最终结果
    
29. 
    
30.     // 释放内存
    
31.     for(int i=0;i<=n;i++) delete[] dp[i];
    
32.     delete[] dp;
    
33.     delete[] a;
    
34.     return 0;
    
35. }

复制代码

空间优化：

通过滚动数组技术将空间复杂度从O(nm)降低到O(m)。核心思想是发现每次状态转移只依赖于前一轮的状态，因此只需要维护两行数组即可。

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. int main()
   
5. {
   
6.     int n,m;  // n菜品数，m总金额
   
7.     cin>>n>>m;
   
8.     int a;  // 当前菜品价格
   
9.    
   
10.     // 只申请两行的滚动数组
    
11.     int** dp=new int*[2];
    
12.     for(int i=0;i<2;i++){
    
13.         dp[i]=new int[m+1]{0};  // 初始化为0
    
14.     }
    
15.     dp[0][0] = 1;  // 基础状态
    
16.    
    
17.     bool now=0;  // 当前行标识(0/1)
    
18.     for(int i=1;i<=n;i++){
    
19.         cin>>a;
    
20.         for(int j=1;j<=m;j++){
    
21.             if(j<a) dp[now][j]=dp[now^1][j];
    
22.             else if(j==a) dp[now][j]=dp[now^1][j]+1;
    
23.             else dp[now][j]=dp[now^1][j]+dp[now^1][j-a];
    
24.         }
    
25.         now^=1;  // 切换当前行
    
26.     }
    
27.     cout<<dp[now^1][m];  // 输出最终结果
    
28.    
    
29.     // 释放内存
    
30.     for(int i=0;i<2;i++) delete[] dp[i];
    
31.     delete[] dp;
    
32.     return 0;
    
33. }

复制代码

C++

转自：从零到一掌握背包问题：洛谷P1164题解精讲，附带优化