洛谷 题解 P1757 【通天之分组背包】上正题

真心不知道楼下写题解的大佬们为什么不压空间（精益求精嘛）

01背包大家都会吗?(不会请回去自习)

别别别，回来回来!给初学者们一个福利

注释就不写了，都看懂了吧
Zero_One_Pack：
#include<iostream>
#include<cmath>
#include<algorithm>
int m,t,w[101],c[101],dp[1001];
using namespace std;
int main()
{
cin>>t>>m;
for (int i=1;i<=m;i++) cin>>w[i]>>c[i];
int maxx=0;
for (int i=1;i<=m;i++)
{
for (int j=t;j>=w[i];j--)
//重点
{
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
if (dp[j]>maxx) maxx=dp[j];
}
}
cout<<maxx<<endl;
return 0;
}
Complete_Pack:
#include<iostream>
#include<cmath>
#include<algorithm>
//我无聊
int m,t,w[11001],c[11001],dp[11001];
using namespace std;
int main()
{
cin>>t>>m;
for (int i=1;i<=m;i++) cin>>w[i]>>c[i];
int maxx=0;
for (int i=1;i<=m;i++)
{
for (int j=w[i];j<=t;j++)
{
//调换循环顺序，可以自己手推一下 （重点）
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
if (dp[j]>maxx) maxx=dp[j];
}
}
cout<<maxx<<endl;
return 0;
}

上正题

我们可以根据《背包九讲》里的讲解得到如下代码：

#include<iostream>
using namespace std;
int f[10001],n,m,w[1001],c[1001],a[101][1001];
int main(){
cin>>m>>n;int maxx=0;
for(int i=1,k;i<=n;i++){
cin>>w[i]>>c[i]>>k;
a[k][++a[k][0]]=i;
maxx=max(k,maxx);
}
......

但如果数据再大点呢?

MLE

so...

对了，降维是一个有效解决此类问题的办法!

滚动数组？可以可以，但有没有更好的办法呢?

有！

我们可以从上面的01背包中获得启示，当前状态的更优解

只会从前面来

所以

dp[105][1005]->dp[2][1005]->dp[1005]!

妈妈再也不用担心我的内存！

上代码：
#include<bits/stdc++.h> /*1<=m<=1000 1<=n<=1000 组数t<=100*/ //好习惯 int dp[1005],w[1005],c[1005],g[1005]; //没骗你，是一维，dp[j]表示背包内物品为j时获得的的最大价值 using namespace std; int main(){ int n,m; scanf("%d%d",&m,&n); int group=-1; for(int i=1;i<=n;++i){ scanf("%d%d%d",&w[i],&c[i],&g[i]); group=max(group,g[i]); }//输入确定组数 for(int i=1;i<=group;++i){//枚举组 for(int j=m;j>=0;--j){//枚举重量（非常巧妙地避开了相互冲突，自己手推才会更好理解） for(int k=1;k<=n;++k){//枚举物品 if(g[k]!=i||j<w[k])continue;//装不下 dp[j]=max(dp[j],dp[j-w[k]]+c[k]);//见《背包九讲》 } } } printf("%dn",dp[m]);//输出answer return 0;//请勿抄袭 }

总之，背包就是列表法，把表列出来了，什么混合背包，分组背包，多重背包，一点也不难。