不会就不要做
by 览遍千秋 @ 2017-10-28 19:55:01
建议可以先去学一学背包,先学01背包和完全背包
01背包模板:
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int w[3405],d[3405],dp[12885];//w是价值,d是体积,dp[i]是当你还又d个体积是能拿到的最大价值
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d%d",&w[i],&d[i]);
for(int i=0;i<n;i++)
{
for(int j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
}
printf("%d",dp[m]);
return 0;
}
```
by noble_ @ 2017-10-28 19:57:34
推荐背包九讲,百度一下就有,要是要深入理解背包建议看一看
by panda_2134 @ 2017-10-28 20:59:26
```cpp
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
int t,m,tim[110],mon[110],mm[1100]={0};
cin>>t>>m;
for(int i=1;i<=m;i++)
cin>>tim[i]>>mon[i];
for(int i=1;i<=m;i++)
for(int j=t;j>=tim[i];j--)
mm[j]=max( mm[j-tim[i]]+mon[i],mm[j]);
cout<<mm[t];
return 0;
}
```
by Freddie @ 2017-10-30 13:50:44
我少复制了#include<iostream>
by Freddie @ 2017-10-30 13:56:48
一维老师讲的
```cpp
#include<iostream>
using namespace std;
//int f[1001][1001];
int f[1001],n,w[1001],v[1001],c;
int main(){
int i,j;
cin>>c>>n;
for(i=1;i<=n;i++)
cin>>w[i]>>v[i];
for(i=1;i<=n;i++)
for(j=c;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+v[i]);
cout<<f[c];
return 0;
}
```
by 升阳 @ 2017-10-30 22:56:05
直接搜索就能过
by Jigsaw_Killer @ 2017-11-08 06:01:26
```cpp
#include <cstdio>
const int maxn = 5005;
int dp[maxn][maxn],t,n,w[maxn],v[maxn],V;
int max(int a,int b){
if(a>b)return a;
else return b;
}
int main() {
scanf("%d%d",&V,&n) ;
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for (int i=1;i<=n;i++)
for (int j=0;j<=V;j++)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
int ans=dp[n][V];
printf("%d",ans);
}
我这个怎么结果不对呢?
```
by 企鹅 @ 2017-12-10 14:24:23