背包问题可以分为

0-1背包(每件物品都只有一件)

完全背包(每件物品都有无数件)

多重背包(每件物品可以有多件)

当然,我们的 背包 肯定是有 容量大小的(看题目规定或者自己输入)。

首先推荐一下0-1背包问题的解析 https://blog.csdn.net/AC__GO/article/details/76918559

然后再解决一下我自己当时有点迷糊的点

0-1背包 的思路其实就是这样

 

当前背包的容量能不能放的下当前物品

如果能

要放下当前物品要执行什么操作(要不要拿出来之前放的物品)

执行完操作

放入当前物品后的总价值    是否大于  不放入当前物品的总价值

按照这个思路去看上面推荐的解析应该就能明白了。。。。。。。

——————————————————————————————————————————————————————————————————————————————————————————

本来一直都是用打表,今天被一道题卡超时,没办法就学了下,发现没那么难。

#include<iostream>
using namespace std;
#define inf 1000005
int num[inf];//这个是所有数的数组,等于0就代表为素数,等于1就代表合数
int book[inf];//这个是专门放素数的数组
int main()
{
    int n, t = 1;//n是范围,t=1是因为 素数的数组 要用
    cin >> n;//读入范围
    for (int i = 2; i <= n; i++) {//开始遍历
        if (num[i] == 0) { book[t++] = i; }//如果这个数是素数,那就放入素数的数组
        for (int j = 1; j < t && (book[j]*i<inf); j++) {
            num[i*book[j]] = 1;//当前数*素数=一个合数   把这个合数标记为1 代表是合数
            if (!(i % book[j])) { break; }//如果找到了自己的最小质因数,那就跳出
        }
    }
}
/*数学小知识:每一个合数 都至少整除 一个素数 
比如 6能整除2   那么2就是6的最小质因数*/

这几天有点水。。。。。。。。。