01背包问题——记忆化搜索的妙用

题目最基本的想法

思想

引申

解决方案解决方案代码 其他解法

==memset原理==

#include

using namespace std;

int n,W;
const int MAX_SIZE=100;
int w[MAX_SIZE+1],v[MAX_SIZE+1];

void solve();
int rec(int,int);


int main(){
    cin >> n >> W;
    for(int i=0;i> w[i] >> v[i];
    }
    solve();
}

void solve(){
    cout << rec(0,W);
}

int rec(int i,int j){//i表示从第几件物品开始取，j表示能取的容量还有多少
    int res;//每一层都会有一个叫做res的变量,用于记录当前层数下的背包价值
    if(i==n){//物品的编号是从0~n-1的，这里==n表示已经取到头了
        res=0;
    }else if(j 
思想 
这种解法的思想就是
 要知道在容量为W，可选物品为0~n-1的情况最大价值是多少
 我们就去寻找
 
在容量为W，可选物品为1~n-1的情况最大价值是多少（不拿第1件物品之后）在容量为W-j，可选物品为1~n-1的情况最大价值是多少（拿第一件物品之后）
 这样递归的结构一目了然
 然后我们再把当前层的最优解存在res里，层层返回，就得到了最终的最优解
 输出即可
 

  这里我们还可以发现，递归都是从复杂问题入手，逐渐变成简单问题，且具有相同子结构~ 

引申 
可能已经有读者已经发现了，上面的形式与二叉树相似，因此我们可以说它的复杂度为n2 ，因此，当n比较大的时候，翻车是必然的。除此之外还可能会出现重复计算的问题。
 
 
 
解决方案 
因此，我们可以用一个数组把内容记录下来，这样用到的时候直接调用即可。
 
解决方案代码 
#include

using namespace std;

int n,W;
const int MAX_SIZE=100;
int w[MAX_SIZE+1],v[MAX_SIZE+1];
int record[110][1010];// todo 用于记录每次res的值

void solve();
int rec(int,int);


int main(){
    cin >> n >> W;
    for(int i=0;i> w[i] >> v[i];
    }
    solve();
    system("pause");
    return 0;
}

void solve(){
    cout << rec(0,W);
}

int rec(int i,int j){
    if(record[i][j]==0){
        int res;
        if(i==n){
            res=0;
        }else if(j 
超时的问题迎刃而解~
 
 
其他解法 
我们可不可以不利用递归写呢？答案是可以
 复杂度也是n*W，其实和上文思路是一样的，但是这里我们用两个for循环
 
假设当前背包容量为V，物品的价值为val，体积为wgt，我们要考虑的就是这个物品要不要拿？那么怎么进行比较呢，我们可以用背包容量为V-wgt时的价值+val（相当于拿这个物体），与现在容量为V时的价值进行比较（也就相当于不拿这个物品），如果前者的价值更高，那么就选择拿这个物体，如果不拿这个物体时的价值高，那么就不拿这个物体。
 这个想法有点绕，笔者拙笨，不能清楚的讲述出来，更多内容可参见大佬的背包九讲。
 
#include
#include
using namespace std;

int n,W;//n表示物品数量,W表示背包容量

struct thing
{
    int _w,_v;
    thing(int w,int v){
        this->_w=w;
        this->_v=v;
    }
    thing(){};
};


int main(){
	cin >> n >> W;
    thing T[110];
	for(int i=0;i> T[i]._w >> T[i]._v;
	}
    int w[1010]={0};
    //首先肯定是双重循环控制，外层循环控制是哪个物品
    //内层循环控制背包当前容量
    for(int i=0;i=0;j--){//这里的容量就是从W开始计算的，并不用考虑W-1
            int v=j-T[i]._w;
            if(v>=0){
                w[j]=max(w[j],w[v]+T[i]._v);
            }
        }
    }
    //迭代完成，查看最终结果
    cout << w[W] << endl;
    return 0;
}

// todo 我们的思路是



 
顺带一提，使用包含在cstring中的memset(array,val,sizeof(array))函数可以快速初始化高维数组的值为指定的值(val)。包含的头文件不能写成string，必须是cstring。
 注意！！！不能将数组的值设为1等其他值
 
 
可以设置成0或-1
 
 
 
memset原理 
memset修改的是内存，一次直接修改一个字节（8位），而我们的数组是32位int型的，如果设置成1的话用2进制来表示是00000001，一共表示4次，得到的值换算成10进制就是
 
 
那么为什么可以刷成0或-1呢？
 0自然不必解释00000000
 -1就涉及到补码的知识了
 在计算机组成原理中我们学过原码反码补码
 我们知道-1的原码是符号位加上真值的绝对值，因此-1的原码是10000001，将-1的原码转换为反码，方法是符号位保持不变，其余按位取反，因此-1的反码是11111110，最后将反码转换为补码，末位+1，符号位保持不变，得到-1的补码11111111，因此我们可以利用memset快速将数组赋值成-1~