秋招突击——6/23——复习{完全背包问题——买书，状态转换机——股票买卖V}——新作{两数相除}

引言

• 今天起的挺早的，昨天的题目也刷完了，两道简单题，最后的KMP也没看，应用面太窄了，考到了，只能放弃喽。
• 今天继续，把那个完全背包问题解决了。

复习

完全背包问题——买书

背包问题差不多已经做了四遍，对应的链接如下

• 二维背包问题
• 第一次讲买药的背包问题

回归一下题目，如果要看上一次的分析，就看上面那个链接

个人实现

• 这里做了一些推理，其实之前担心要完整放一次，也就是同时包含所有类型的物体，才会不重不漏地放完，怀疑动态规划针对单个物体的放会出现遗漏。
• 实际上不会，第一个物体的所有情况已经被遍历过了，后续再放其他的物体是建立在第一个物体的所有情况的基础上，所以就不会存在遗漏的情况。

• 最终代码实现如下

#include <iostream>
using namespace std;

const int N = 1010;
int p[5] = {
   0,10,20,50,100};
int n,f[5][N];

int main(){
   
    cin>>n;
    for (int i = 1; i <= 4; ++i) {
   
        // 遍历不同的物体
        for (int j = 1; j <= n; ++j) {
   
            // 遍历不同的金钱数量
            for (int k = 0; k * p[i] <= j; ++k) {
   
                // 遍历不同的数量
                f[i][j] = f[i - 1][j] + f[i -1][j - k * p[i]];
            }
        }
    }
    // 然后便利容量为5的情况
    int res = 0;
    for (int i = 1; i <= 4; ++i) {
   
        res += f[i][n];
    }
    cout<<res;
}

问题

• 在实现过程中，不是很清楚边界点的确定，只能单纯依靠的数组的索引的关系进行判定，保证索引不越界。
• 对于集合的划分，也就是状态转移还是有点问题，不能保证他的结果是相同的。

参考实现

朴素实现

• 这里没有照抄，对照着改了一下我的代码，这里有以下几个问题需要注意
  • 我大部分地方都是对的，但是最终输出应该是所有的情况累加和，f[4][n]就已经包含了之前所有的情况的累加和，所以并不需要进行更改。
  • 需要将f[0][0]初始化为0，其实没有什么特殊的情况，这里就是检查一下，有没有用到没有初始化的初始值

#include <iostream>

using namespace std;

const int N = 1010;
int p[5]