168 条题解

  • 3
    @ 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
    @ 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
    @ 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
    找出错误点

  • 1
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2017-03-13 18:31:58

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

  • 1
    @ 2017-03-12 20:57:50

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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]);
    }```
    
  • 0
    @ 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
    @ 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;
    }

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

      include前面的#没复制上去

  • 0
    @ 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
    @ 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
    @ 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;
    }

信息

ID
1334
难度
2
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
2916
已通过
1743
通过率
60%
被复制
5
上传者