168 条题解
-
3
Michael112233 LV 8 @ 8 年前
#include<bits/stdc++.h>
using namespace std;
int f[500][500],v[50],ka[50],m[50];
int main()
{
int V,M,n;
scanf("%d%d%d",&V,&M,&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&v[i],&m[i],&ka[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=V;j>=0;j--)
{
for(int k=M;k>=0;k--)
{
if(j>=v[i]&&k>=m[i])
{
f[j][k]=max(f[j-v[i]][k-m[i]]+ka[i],f[j][k]);
}
}
}
}
printf("%d\n",f[V][M]);
} -
27 年前@
三重循环,二维数组
var
m1,t,n,i,j,k:longint;
m,v,w:array[0..500]of integer;
f:array[0..600,0..600]of integer;
begin
readln(m1,t);
readln(n);
for i:=1 to n do readln(m[i],v[i],w[i]);
for i:=1 to n do
for j:=m1 downto 1 do
for k:=t downto 1 do
if (j>=m[i])and(k>=v[i]) then begin
if f[j,k]<f[j-m[i],k-v[i]]+w[i] then
f[j,k]:=f[j-m[i],k-v[i]]+w[i];
end;
writeln(f[m1,t]);
end. -
28 年前@
var
i,j,n,m,v,k:longint;
f:array[1..1000,1..1000] of longint;
a,b,c:array[1..2000] of longint;
begin
readln(v,m);
readln(n);
for i:=1 to n do
readln(a[i],b[i],c[i]);
for i:=1 to n do
for j:=v downto a[i] do
for k:=m downto b[i] do
if f[j-a[i],k-b[i]]+c[i]>f[j,k] then f[j,k]:=f[j-a[i],k-b[i]]+c[i];
writeln(f[v,m]);
end.
Wrong Answervar
i,j,n,m,v,k:longint;
f:array[0..400,0..400] of longint;
a,b,s:array[0..50] of longint;
begin
readln(v,m);
readln(n);
for i:=1 to n do
readln(a[i],b[i],s[i]);
for i:=1 to n do
for j:=v downto a[i] do
for k:=m downto b[i] do
if f[j-a[i],k-b[i]]+s[i]>f[j,k] then f[j,k]:=f[j-a[i],k-b[i]]+s[i];
writeln(f[v,m]);
end.
AC
找出错误点 -
15 年前@
看大家这么稳,我就放心了,注意如果循环是从小往大就是可重复背包,从大往小才是不可重复背包。
-
16 年前@
SO H2O
-
17 年前@
#include<iostream>
using namespace std;struct T{
int v;//体积
int m;//质量
int s;//能量
};
int f[50][400][400];
T a[50];
int v, m, n;
int main(){
//freopen("test.txt", "r", stdin);
cin>>v>>m;
cin>>n;
int i, j, k;
for(i = 1; i <= n; ++i){
cin>>a[i].v>>a[i].m>>a[i].s;
}
f[0][0][0] = 0;
for(i = 1; i <= n; ++i){
f[i][0][0] = 0;
for(j = 1; j <= v; ++j){
f[i][j][0] = 0;
for(k = 1; k <=m; ++k){
f[0][j][k] = 0;if(a[i].v <= j && a[i].m <= k){
f[i][j][k] =
max(f[i - 1][j - a[i].v][k - a[i].m] +
a[i].s, f[i - 1][j][k]);
}else{
f[i][j][k] = f[i - 1][j][k];
}
}
}
}
cout<<f[n][v][m];
return 0;
} -
17 年前@
#include<bits/stdc++.h>
using namespace std;
inline const void read(int &a)
{
a=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
}
int n,f[2][401][401],v[41],w[41],c[41],maxv,maxw;
int main()
{
memset(f,0,sizeof(f));
read(maxv);read(maxw);read(n);
for(int i=1;i<=n;i++){read(v[i]);read(w[i]);read(c[i]);}
for(int i=1;i<=n;i++)
for(int j=1;j<=maxv;j++)
for(int k=1;k<=maxw;k++)
{
if(v[i]<=j&&w[i]<=k)f[i%2][j][k]=max(f[i%2^1][j][k],f[i%2^1][j-v[i]][k-w[i]]+c[i]);
else f[i%2][j][k]=f[i%2^1][j][k];
}
cout<<f[n%2][maxv][maxw];
return 0;
} -
18 年前@
-
18 年前@
-
1
-
07 年前@
-
07 年前@
#include <iostream>
#include <algorithm>
using namespace std;int main(){
int a, b, n, v, w, p, r[400][400] = { 0 };
cin >> a >> b;
cin >> n;
for (int c = 0; c < n; c++){
cin >> v >> w >> p;
for (int i = a; i>=v;i--)
for (int j = b; j >= w; j--)
{
r[i][j] = max(r[i-v][j-w] + p, r[i][j]);
}
}
cout << r[a][b]<<endl;return 0;
} -
07 年前@
DP第三题。◕‿◕。
-
07 年前@
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,v,a[10009],b[10009],c[10009],f[10009][10009];
int main()
{
cin>>v>>m>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i]>>c[i];
for(int i=1;i<=n;i++)
for(int j=v;j>=a[i];j--)
for(int k=m;k>=b[i];k--)
f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+c[i]);
cout<<f[v][m];
return 0;
} -
08 年前@
-
08 年前@
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int n,i,j,a,f[402][402]={0},v,m,k,bigm,bigv;
scanf("%d%d%d",&bigv,&bigm,&n);
for(i=1;i<=n;i++){
scanf("%d%d%d",&v,&m,&k);
for(j=bigm;j>=m;j--)
for(a=bigv;a>=v;a--)
f[j][a]=max(f[j][a],f[j-m][a-v]+k);}
printf("%d",f[bigm][bigv]);
return 0;} -
08 年前@
//f[i][j]代表在有体积为i,质量为j时存储的最多脂肪
#include<iostream>
using namespace std;
int main()
{
int n,m,i,j,f[400][400];
int x,y;
cin>>x>>y;
cin>>n;
int w,q,c;
for(i=0;i<=x;i++)
for(j=0;j<=y;j++) f[i][j]=0;
for(i=1;i<=n;i++)
{
cin>>w>>q>>c;
for(j=x;j>=w;j--)
for(int l=y;l>=q;l--)
f[j][l]=max(f[j][l],f[j-w][l-q]+c);
}
cout<<f[x][y];
return 0;
} -
08 年前@
-
08 年前@
01背包
-
08 年前@
#include <iostream>
#include <stdio.h>using namespace std;
int v[55], w[55],p[55];
int f[500][500];
int main()
{
int va,wa;
int n;
scanf("%d %d %d", &va, &wa, &n);
int i, j, k;for(i = 1; i <= n; i++)
scanf("%d%d%d", &v[i],&w[i],&p[i]);
int ma = 0;for(i = 1; i <= n; i++)
{
for(j = va; j >=v[i]; j--)
{
for(k = wa; k >= w[i]; k--)
{
f[j][k] = max(f[j][k], f[j-v[i]][k-w[i]]+p[i]);
ma = max(ma, f[j][k]);
}
}
}printf("%d", ma);
return 0;
}