AWA

部分板子优化中...

你好哇，我是flypig114

代码里有变量数组的注释，so...不多废话，直接上正题！

01背包

无优化

<code>#include<bits/stdc++.h>

using namespace std;

#define ll int//为了方便修改类型

const ll N=1000;//辅助定义数组

ll n,m;//n是背包容量 m是物品数量

ll v[N], w[N];//v是物品的重量 w是物品的价值

ll i,j,dp[N][N];//辅助计算

int main()

{

//背包与DP的开始

cin>>n>>m;

for(i=1;i<=m;i++)

{

cin>>v[i]>>w[i];

}

//进行处理

for(i=1;i<=m;i++)

for(j=n;j>=0;j--)

{

if(j>=v[i])

{

dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);

}

else

{

dp[i][j]=dp[i-1][j];

}

}

//结束首战告捷

cout<<dp[m][n];

return 0;

}

一维数组优化：

#include<bits/stdc++.h>

using namespace std;

#define ll int//为了方便修改类型

const ll N=1e5;//辅助定义数组

ll n,m;//n是背包容量 m是物品数量

ll v[N], w[N];//v是物品的重量 w是物品的价值

ll i,j,dp[N];//辅助计算

int main()

{

//难度上升需要新方法

cin>>n>>m;

for(i=1;i<=m;i++)

{

cin>>v[i]>>w[i];

}

//重中之重（好像就这里改了）

for(i=1;i<=m;i++)

{

for(j=n;j>=0;j--)

{

if(j>=v[i])

{

dp[j]=max(dp[j-v[i]]+w[i], dp[j]);

}

}

}

//可以输出了

cout<<dp[n];

return 0;

}

更进一步的常数优化：

#include<bits/stdc++.h>

using namespace std;

#define ll int//为了方便修改类型

const ll N=1000;//辅助定义数组

ll n,m;//n是背包容量 m是物品数量

ll v[N], w[N];//v是物品的重量 w是物品的价值

ll i,j,dp[N],lower,sum;//辅助计算

int main()

{

//还要优化

cin>>n>>m;

for(i=1;i<=m;i++)

{

cin>>v[i]>>w[i];

}

//重中之重（这话怎么这么熟悉）

for(i=1;i<=n;i++)

{

if(i!=1)

{

sum+=v[i-1];

}

lower=max(m-sum,v[i]);

for(j=n;j>=lower;j--)

{

//if(j>=v[i])

dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

}

}

//赶紧的输出

cout<<dp[n];

return 0;

}

完全背包问题：

#include<bits/stdc++.h>

using namespace std;

#define ll int//为了方便修改类型

const ll N=1e5;//辅助定义数组

ll n,m;//n是背包容量 m是物品数量

ll v[N], w[N];//v是物品的重量 w是物品的价值

ll dp[N],i,j;//辅助计算

int main(){

cin>>n>>m;

//输入

for(i=1;i<=n;i++)

{

cin>>v[i]>>w[i];

}

//完全背包启动！

for(i=1;i<=n;i++)

{

for(j=0;j<=m;j++)

{

if(j>=v[i])

dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

}

}

//简简单单的输出

cout<<"max="<<dp[m]<<endl;

return 0;

}

多重背包问题：

无优化

#include<bits/stdc++.h>

using namespace std;

#define ll int//为了方便修改类型

const ll N=1000;//辅助定义数组

ll m,n;//n是背包容量 m是物品数量

ll v[N],w[N],s[N];//v是物品的重量 w是物品的价值 s是物品的数量。

ll dp[N][N],i,j,k;//辅助计算

int main()

{

//忘说了输入顺序按需求更改（不会有人真题都不看就套板子吧？）

cin>>m>>n;

for(i=1;i<=m;i++)

{

cin>>v[i]>>w[i]>>s[i];

}

//熟悉的流程

for(i=1;i<=m;i++)

{

for(j=0;j<=n;j++)

{

for (k=0;k<=s[i]&&k*v[i]<=j;k++)

{

dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);

}

}

}

//结束了？

cout<<dp[m][n]<<endl;

return 0;

//结束了。

}