每日练习之完全背包——兑换零钱，完全背包问题总结

兑换零钱

题目描述

运行代码

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int mod=1e9+7;
int a[20]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000},dp[100010];
int main()
{
  dp[0]=1;
  for(int i=0;i<13;i++)
        for(int j=a[i];j<=100000;j++)
            dp[j]=(dp[j]+dp[j-a[i]])%mod;
  int N,T;
  cin>>T;
  while( T-- )
  {
    cin>>N;
    cout<<dp[N]<<endl;
  }
   return 0;
}

代码思路

1. 初始化dp[0]为1，因为凑成面额0只有一种方式（即不使用任何硬币）。
2. 使用两个嵌套的循环来计算dp数组的其他元素。外层循环遍历硬币数组a，内层循环遍历从当前硬币面额到100000的所有可能面额。对于每个面额j，我们都检查是否可以使用当前硬币a[i]来凑成它。如果可以（即j >= a[i]），则dp[j]的值是原来的值加上dp[j-a[i]]（即不使用当前硬币和使用当前硬币的凑法数之和）。
3. 最后，程序读取测试用例数量T，然后对每个测试用例读取一个整数N，并输出dp[N]，即凑成面额N的方法数。

改进建议

1. 避免使用<bits/stdc++.h>：这个头文件虽然包含了几乎所有标准库，但它不是标准C++的一部分，而且会增加编译时间。建议只包含你需要的头文件。
2. 数组大小：虽然这里定义dp数组的大小为100010是足够的，但如果你想要一个更通用的解决方案，你可以根据输入的最大可能值来动态分配这个数组的大小。
3. 输入验证：虽然在这个问题中可能不需要，但在实际应用中，验证输入的有效性（例如，确保N是非负的）是一个好习惯。
4. 注释：添加注释来解释代码的每个部分是如何工作的，以及为什么选择这种特定的实现方式，可以帮助其他人（或未来的你）更容易地理解代码。
5. 优化：虽然对于这个问题来说，当前的实现已经足够快，但如果你在处理更大的面额或更多的硬币时，你可能需要考虑更高效的算法，如使用背包问题的优化技术。

改进代码

#include <iostream>  
#include <vector>  
using namespace std;  
const int MOD = 1e9 + 7;  
const int MAX = 100000; 
vector<int> coin = {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};  
// 动态规划表，用于存储凑成不同面额的方法数  
vector<int> Amount(MAX + 1, 0);  
int main() {  
    // 初始化凑成面额0的方法数为1  
   Amount[0] = 1;   
    // 动态规划计算凑成不同面额的方法数  
    for (int i = 0; i < coin.size(); i++) {  
        for (int j = coin[i]; j <= MAX; j++) {  
            Amount[j] = (Amount[j] + Amount[j - coin[i]]) % MOD;  
        }  
    }  
    int T, N;  
    cin >> T; // 读取测试用例数量   
    while (T--) {  
        cin >> N; // 读取当前测试用例的面额  
        cout <<Amount[N] << endl; // 输出凑成面额N的方法数  
    }   
    return 0;  
}

完全背包问题

完全背包问题是一个经典的动态规划问题，其特点在于每种物品都有无限个，可以选择放入背包中的数量不受限制。

总结

1. 问题描述：给定N种物品和一个容量为W的背包，每种物品都有无限个可用，每种物品的重量是weight[i]，价值是value[i]。求解将哪些物品装入背包，可以使得装入背包的物品总价值最大，且不超过背包的容量限制。
2. 状态定义：设dp[i][j]表示前i种物品，在背包容量为j的情况下所能获得的最大价值。或者，也可以使用一维数组dp[j]，其中dp[j]表示背包容量为j时的最大价值。
3. 状态转移方程：对于一维数组的情况，状态转移方程为dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，其中i表示当前考虑的物品，j表示当前背包的容量。这个方程表示，对于第i种物品，可以选择放入或不放入背包，取两种情况下的价值较大者作为当前背包容量的最大价值。

注意事项

• 初始化：在动态规划问题中，初始化的设置非常关键。对于完全背包问题，通常需要将dp数组初始化为0，表示没有任何物品放入背包时的价值为0。
• 遍历顺序：与01背包问题不同，完全背包问题在遍历背包容量时可以从前往后遍历，因为每种物品都可以选择放入多个。而在01背包问题中，为了避免重复计算，需要从后往前遍历背包容量。
• 空间优化：在实际编程中，为了节省空间，可以使用一维数组代替二维数组进行状态转移。但是需要注意，由于完全背包问题中每种物品都可以选择放入多个，因此在遍历背包容量时，内部循环应该是从前往后遍历。
• 避免重复计算：在编写代码时，要注意避免重复计算。例如，在遍历过程中，对于同一种物品，如果已经计算过在某种背包容量下的最大价值，那么就不需要再次计算。
• 边界条件处理：在处理边界条件时，要特别小心。例如，当背包容量为0时，无论放入何种物品，其价值都应为0；当物品重量超过背包容量时，该物品无法放入背包。这些情况都需要在代码中妥善处理。
• 理解问题背景：在解决完全背包问题时，要深入理解问题的背景和要求。例如，有些问题可能要求输出具体的装入方案，而不仅仅是最大价值。在这种情况下，需要在代码中记录装入方案的相关信息。