题解 - Vijos

3

Michael112233 LV 8 @ 2016-12-06 22:00:45

#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]);
}

2

李暑涵 LV 8 @ 2017-07-19 17:19:44

三重循环，二维数组
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.

2

xieshihua LV 9 @ 2016-09-02 22:23:20

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 Answer

var
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
找出错误点

EddieLi @ 2024-08-04 09:25:25

这到底是啥语言啊

1

Lifi LV 10 @ 2019-07-28 20:58:54

看大家这么稳，我就放心了，注意如果循环是从小往大就是可重复背包，从大往小才是不可重复背包。

#include <iostream>

using namespace std;

int dp[401][401]={0};
int mv,mm;

int main()
{
    cin>>mv>>mm;
    int n,v,m,ka,i,j;
    cin>>n;
    while(n>0)
    {
        n--;
        cin>>v>>m>>ka;
        for(i=mv;i>=v;i--)
        {
            for(j=mm;j>=m;j--)
            {
                dp[i][j]=max(dp[i][j],dp[i-v][j-m]+ka);
            }
        }
    }
    cout<<dp[mv][mm]<<endl;
    return 0;
}

1

血色X战魂 LV 8 @ 2019-01-16 17:45:47

SO H2O

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//呵呵
//大神万岁
//分割线--------------------------------------------------$
//结构定义区
struct thing{
    int v;
    int h;
    int k;
    thing()
    {
        v=0;k=0;h=0;
    }
};
//全局变量区
long long f[401][401],n,V,H;
thing t[51];
//函数声明区

//主函数开始！
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>V>>H>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i].v>>t[i].h>>t[i].k;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=t[i].v;j--)
        {
            for(int k=H;k>=t[i].h;k--)
            {
                f[j][k]=max(f[j][k],f[j-t[i].v][k-t[i].h]+t[i].k);
            }
        }
    }
    cout<<f[V][H];
    return 0;
}
//函数实现区

1

gss LV 8 @ 2017-09-05 22:32:57

#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;
}

1

Randle LV 9 @ 2017-08-08 11:21:39

#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;
}

1

学习阶段的刘锦钰 LV 9 @ 2017-03-13 18:31:58

大家看一下，我的解题报告
http://blog.csdn.net/qq_35904657/article/details/61634934

1

学习阶段的刘锦钰 LV 9 @ 2017-03-12 20:57:50

大家看一下，我的解题报告
http://blog.csdn.net/qq_35904657/article/details/61634934

1

学习阶段的刘锦钰 LV 9 @ 2017-03-12 20:57:20

大家看一下
http://blog.csdn.net/qq_35904657/article/details/61634934

0

Hzc492 LV 8 @ 2018-02-20 12:42:44

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i <= _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i >= _##i; --i)
#define mem(f,x) memset(f,x,sizeof(f))
//========================================================================
int f[405][405];
int c1[55], c2[55], v[55];
int n, m, w;
int main()
{
    cin >> w >> m;
    cin >> n;
    FOR(i, 1, n) cin >> c1[i] >> c2[i] >> v[i];
    mem(f, 0);
    FOR(k, 1, n) {
        FORD(j, w, c1[k]) {
            FORD(i, m, c2[k]) {
                f[j][i] = max(f[j][i], f[j - c1[k]][i - c2[k]] + v[k]);
            }
        }
    }
    cout << f[w][m];
    return 0;
}

0

shadow1111 LV 4 @ 2018-01-01 16:40: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;
}

0

伊人 LV 8 @ 2017-11-01 16:29:41

DP第三题｡◕‿◕｡

#include<iostream>
using namespace std;
int dp[55][405][405],v[55],m[55],w[55];
int V,M,n;
int main()
{
    cin>>V>>M>>n;
    for(int i=1;i<=n;++i)
    cin>>v[i]>>m[i]>>w[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])
                dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-v[i]][k-m[i]]+w[i]);
                else
                dp[i][j][k]=dp[i-1][j][k];
            }
        }
    }
    cout<<dp[n][V][M];
    return 0;
}

0

yyyz119 LV 8 @ 2017-09-07 21:57:40

#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;
}

0

cdqzgxxqdql LV 10 @ 2016-10-20 14:56:23

#include<iostream>
using namespace std;
int v[51],m[51],k[51],f[401][401];
int main()
{
    int V,M,n;
    cin>>V>>M>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>m[i]>>k[i];
    for(int i=1;i<=n;i++)
        for(int vv=V;vv>=0;vv--)
            for(int mm=M;mm>=0;mm--)
                if(vv>=v[i]&&mm>=m[i])
                    f[vv][mm]=max(f[vv-v[i]][mm-m[i]]+k[i],f[vv][mm]);
    printf("%d",f[V][M]);
}```

学习阶段的刘锦钰 @ 2017-03-13 18:32:36

这不是楼下的吗？
学习阶段的刘锦钰 @ 2017-03-13 18:32:53

@学习阶段的刘锦钰: 楼下的楼下的楼下的……

0

noi031 LV 10 @ 2016-09-24 10:03:56

#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;}

0

thekeyto LV 8 @ 2016-09-04 21:36:50

//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;
}

thekeyto @ 2016-09-04 21:37:50

include前面的#没复制上去

0

PowderHan LV 10 @ 2016-08-15 20:24:11

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

int f[405][405];
int n;
int V,W;

int main()
{
    int w,v,c;
    cin>>V>>W>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v>>w>>c;
        for(int j=V;j>=v;j--)
        {
            for(int k=W;k>=w;k--)
                f[j][k]=max(f[j][k],f[j-v][k-w]+c);
        }
    }
    cout<<f[V][W]<<endl;
    return 0;
}

0

liuyiah LV 10 @ 2016-08-14 21:30:55

#include <bits/stdc++.h>
using namespace std;
int v[51], w[51], p[51], dp[401][401];
int main()
{
    int maxv, maxw, n, ans = 0;
    scanf("%d%d%d", &maxv, &maxw, &n);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &v[i], &w[i], &p[i]);
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = maxv; j >= v[i]; j--)
        {
            for(int k = maxw; k >= w[i]; k--)
            {
                dp[j][k] = max(dp[j][k], dp[j - v[i]][k - w[i]] + p[i]);
                ans = max(ans, dp[j][k]);
            }
        }
    }
    printf("%d", ans);
    return 0;
}

01背包

0

Asmodians LV 5 @ 2016-08-13 10:46:21

#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;
}

题解

168 条题解

NASA的食物计划

信息

状态

开发

支持

题解

168 条题解

NASA的食物计划

信息

状态

开发

支持

还没有账户？

登录