今天终于可以结！束！啦！
因为下午4:30才考完试，没时间打博客
所以就放到上午去打
（不是我说，都最后一天了打什么比赛啊……
我只希望洛谷的预感是真的…
背包问题
01背包模板（2501 OJ P267）
01背包分为2种状态，一种选，一种不选
01背包可以用一个一维数组来做
2重循环，第一重循环枚举物品，第二重倒序枚举背包容量
题目数据范围：1≤n≤100，1≤m≤1e8，1≤wi≤m, 1≤vi≤1000
01背包为什么要倒序枚举背包容量呢？
代码如下：
#include
using namespace std;
const int M=1e8+5;
int m,n,w[110],v[110],dp[M];
int main()
{
memset(dp,-0x3f3f3f3f,sizeof dp);
cin>>m>>n;
for(int i=1;i>w[i]>>v[i];
dp[0]=0;//特判如果背包容量为0
for(int i=1;i=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
int maxn=0;
for(int i=0;i<=m;i++) maxn=max(maxn,dp[i]);
cout<<maxn;
return 0;
}
完全背包模板
因为每个物品可以选很多次，所以把01背包的第2重循环改成正序就可以了
#include
using namespace std;
const int M=1e8+5;
int m,n,w[110],v[110],dp[250];
int main()
{
memset(dp,-0x3f3f3f3f,sizeof dp);
cin>>m>>n;
for(int i=1;i>w[i]>>v[i];
dp[0]=0;//特判如果背包容量为0
for(int i=1;i<=n;i++)
for(int j=w[i];j<=m;j++)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
int maxn=0;
for(int i=0;i<=m;i++) maxn=max(maxn,dp[i]);
cout<<maxn;
return 0;
}
就这样吧……
明天就可以回去啦！！！！
但是一回去培优班就上课，还是语数英（以前都没有英语的，我 ** 真服了
好歹还是培1，幸好期中考考好了，有30%，不然我就死定了…………
比赛：140/400
真的无语住了，m打成n 了
100分都没了