在n件物品取出若干件放在空间为W的背包里，
每件物品的体积为W1，W2至Wn，
与之相对应的价值为P1,P2至Pn，
对于每个物品只需要考虑选与不选两种情况，
求解将哪些物品装入背包可使价值总和最大。
背包问题，是DP中的经典题型，
而0/1背包是经典中的经典
建议阅读：
B站大佬开讲
模板题：
vijos 0/1背包
进阶练习：
扩展挑战：
可以更好了解和练习
如何做这道题呢？
孔子曰：题目不会就深搜递归
代码1 暴力出奇迹（不建议提交）
#include<bits/stdc++.h>
using namespace std;
int n,ans,m;
int w[1001],c[1001];
void dfs(int t,int q,int k)
{
if(t>n)//选完
{
if(k>ans) ans=k;
return;
}
dfs(t+1,q,k);
if(q+w[t]<=m)dfs(t+1,q+w[t],k+c[t]);//可以就尝试
return;
}
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)cin>>w[i]>>c[i];
dfs(1,0,0);
cout<<ans;
return 0;
}
【孔子】因炸服务器被封号
明显，本题递归会裂开（时间超限）
本题每次递归同一个参数得出的值相同，而出现了反复对同一个参数的递归
对于这种问题，记忆化搜索是一个好的解决方案，并可以AC
f[n][m]表示选到第n个物品，背包用了m时得到的最大价值
代码2： 记忆化搜索
#include<bits/stdc++.h>
using namespace std;
int n,ans,m;
int w[1005],c[1005];
int f[110][1005];//f[n][m]表示选到第n个物品，背包用了m时得到的最大价值
void dfs(int t,int q,int k)
{
if(t>n)
{
if(k>ans) ans=k;
return;
}
if(f[t][q]<=k)
{
f[t][q]=k;
dfs(t+1,q,k);
if(q+w[t]<=m)dfs(t+1,q+w[t],k+c[t]);
}
return ;
}
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)cin>>w[i]>>c[i];
dfs(1,0,0);
cout<<ans;
return 0;
}
本题虽然可以用记忆化搜索AC，
但明显不是最优解。
既然已经可以记忆化搜索了，
那就满足无后效性和阶段性，可以DP求解
f[n][m]表示选到第n个物品，背包用了m时得到的最大价值
从前向后直接枚举，可以放就看是不是当前最优解（是不是最大）
代码3： 二维动态规划
#include<bits/stdc++.h>
using namespace std;
int f[1001][1001],w,c,n,m;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w,&c);
for(int k=0;k<=m;k++)//注意是从0开始!
{
f[i][k]=f[i-1][k];
if(k>=w) f[i][k]=max(f[i][k],f[i-1][k-w]+c);
}
}
printf("%d",f[n][m]);
return 0;
}
假设n和m>=10000,那么这种方法就没用了，
好在天无绝人之路——STL中有个vector,
不过更简单的方法是用滚（渣）动（男）数组
可以发现，f的第一层只使用了i,i-1,m三层,
那如果用一个一维数组,只有f[m]呢？
压力马斯内（赞赏）
在修改第i次前,数组的值就是i-1,直接调用修改，
结束后，f[m]正是原来的f[n][m](当前是第n次修改）
那直接一维啊！
但是，一维时要倒序枚举，
不然就会使用多次（不符合0/1性质，成了完全背包），
而且是for m~w 这个很好理解吧
代码4：一维动态规划
#include<cstdio>
using namespace std;
int n,t,w,v,f[1001];
int max(int x,int y){
if(x>y)return x;
else return y;
}
int main(){
scanf("%d%d",&n,&t);
for(int i=1;i<=t;i++)
{
scanf("%d%d",&w,&v);
for(int j=n;j>=w;j--)
f[j]=max(f[j],f[j-w]+v);
}
printf("%d",f[n]);
}
那么关于0/1背包的讲解就结束了，
如有不对，务必提出