259 条题解

  • 3
    @ 2017-11-08 10:38:15

    样例过了的提交却全错的同学看:

    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<queue>
    #include<cctype>
    #include<algorithm>
    using namespace std;
    int n,t,tt[11000],h[10000],f[10000];
    int main()
    {
        cin>>n;
        cin>>t;
        for(int i=1;i<=n;i++)
            cin>>h[i]>>tt[i];
        for(int i=1;i<=n;i++)
        for(int j=t;j>=tt[i];j--)
        f[j]=max(f[j],f[j-tt[i]]+h[i]);
        cout<<f[t];
        return 0;
    }
    

    你们是不是把输入顺序搞反了?

    先输入高兴值后输入耗费时间

  • 1
    @ 2019-09-16 11:28:36

    这是0/1背包问题,每个娱乐项目要么选要么不选,算作动态规划的入门吧。

    // 1025.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int like[1010] = { 0 }, cost[1010] = { 0 }, f[1010] = { 0 };
    int main()
    {
        int N, t;
        cin >> N >> t;
        for (int i = 0; i < N; i++)
            cin >> like[i] >> cost[i];
        for (int i = 0; i < N; i++)
        {
            for (int j = t; j >= cost[i]; j--)
                f[j] = max(f[j], f[j - cost[i]] + like[i]);
            /*
            从最大时间开始,直到时间等于当前项目的时间。
            当总容量是j的时候,遇到了第i个娱乐项目,那
            么就要比一下:是当前已有情况喜欢程度更高呢
            ,还是把当前时间中的一部分用当前项目来替代
            获得的喜欢程度更高呢?把所有大于当前项目时
            间的f[j]都拿来做上述检查,当遍历完所有项目
            后,最优解就出来了。
            */
        }
        cout << f[t] << endl;
        return 0;
    }
    
  • 1
    @ 2017-05-07 12:57:03
    /*
    裸题~很明显的0/1背包问题
    因为每个活动要么选择一次要么不选
    时间是容量   活动是物品
    直接一次0/1背包就能过了
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    int f[1005];
    int n,T;
    
    int main()
    {
        int w,t;
        scanf("%d%d",&n,&T);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&w,&t);
            for(int j=T;j>=t;j--)
                f[j]=max(f[j],f[j-t]+w);
        }
        printf("%d\n",f[T]);
        return 0;
    }
         
    
  • 1
    @ 2016-04-12 20:47:18

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,t,v[1005][1005],t1[1005],p[1005];
    int main()
    {
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
    cin>>p[i]>>t1[i];
    }
    for(int i=0;i<=t;i++)
    v[0][i]=0;

    for(int i=0;i<=n;i++)
    v[i][0]=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=t;j++)
    {
    if(j>=t1[i])
    v[i][j]=max(v[i-1][j-t1[i]]+p[i],v[i-1][j]);
    else
    v[i][j]=v[i-1][j];
    }
    cout<<v[n][t]<<endl;

    return 0;
    }

  • 0
    @ 2020-08-29 11:26:02

    #inclde <iostream>
    using namespace std;
    int n,t,f[1001],w[1001],v[1001];
    int main()
    {
    cin>>n>>t;
    for(int i=0;i<=n;i++)
    cin>>v[i]>>w[i];
    for(int i=0;i<=n;i++)
    {
    for(int j=t;j>=0;j--)
    if(j>=w[i])
    f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
    cout<<f[t];
    return 0;
    }

  • 0
    @ 2020-08-29 11:25:02

    #include<bits/stdc++.h>
    using namespace std;
    int w[10001],v[10001],a[80003],n,m;
    int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
    for(int j=m;j>=w[i];j--){
    a[j]=max(a[j],a[j-w[i]]+v[i]);
    }
    }
    cout<<a[m];
    return 0;
    }
    求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
    求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
    求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
    求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
    求赞求赞求赞求赞求赞求赞求赞求赞求赞求赞
    求赞求赞求赞求赞求赞求赞求赞求赞求赞
    求赞求赞求赞求赞求赞求赞求赞求赞
    求赞求赞求赞求赞求赞求赞求赞
    求赞求赞求赞求赞求赞求赞
    求赞求赞求赞求赞求赞
    求赞求赞求赞求赞

  • 0
    @ 2020-07-05 10:06:20

    01背包
    滚动数组

    #include <iostream>
    #include <cstdio>
    using namespace std;
    int f[1001]={0};
    int n,m;
    int a,b;
    int main () {
        scanf("%d%d",&n,&m);
        for (int q=1;q<=n;q++) {
            scanf("%d%d",&a,&b);
            for (int w=m;w>=b;w--) {
                f[w]=max(f[w],f[w-b]+a);
            }
        }
        printf("%d\n",f[m]);
        return 0;
    }
    
  • 0
    @ 2019-11-23 15:34:17

    #include<iostream>
    #include<string.h>
    using namespace std;
    int f[100];
    int main(){
    int v,w,t,n;
    cin>>n>>t;
    memset(f,0,sizeof(f));
    while(n--){
    cin>>v>>w;
    for(int i=t;i>=0;i--){
    if(i>=w)f[i]=max(f[i-w]+v,f[i]);
    }
    }
    cout<<f[t]<<endl;
    }

  • 0
    @ 2017-08-31 21:11:10

    var
    f:array[0..1000]of longint;
    like,time:array[1..100]of longint;
    i,j,n,t:longint;
    begin
    readln(n);
    readln(t);
    for i:=1 to n do
    readln(like[i],time[i]);
    fillchar(f,sizeof(f),0);
    for i:=1 to n do
    for j:=t downto 1 do
    if j-time[i]>=0 then if f[j-time[i]]+like[i]>f[j] then f[j]:=f[j-time[i]]+like[i];
    writeln(f[t]);
    end.

  • 0
    @ 2016-06-20 09:32:29

    手写了一个暴力dp,无任何优化,结果。。。AC了。。
    ~~~
    #include <iostream>
    #include <cstdio>
    using namespace std;
    int n,t,A[105],T[105],F[105][1005];
    int main(){
    scanf("%d%d",&n,&t);
    for(int i = 1;i <= n;i++) scanf("%d%d",&A[i],&T[i]);
    for(int i = 1;i <= n;i++)
    for(int j = 1;j <= t;j++)
    if(j >= T[i]) F[i][j] = max(F[i - 1][j],F[i - 1][j - T[i]] + A[i]);
    else F[i][j] = F[i - 1][j];
    printf("%d\n",F[n][t]);
    return 0;
    }

    还是练练优化吧。。。
    

    #include <iostream>
    #include <cstdio>
    using namespace std;
    int n,t,A,T,F[1005];
    int main(){
    scanf("%d%d",&n,&t);
    for(int i = 1;i <= n;i++) {
    scanf("%d%d",&A,&T);
    for(int j = t;j >= T;j--) F[j] = max(F[j],F[j - T] + A);
    }
    printf("%d\n",F[t]);
    return 0;
    }

  • 0
    @ 2016-05-23 18:38:04

    #include <cstdio>

    int max(int a,int b){
    return a>b?a:b;
    }

    int main(){
    // freopen("in.txt","r",stdin);
    int n,v;
    int c[1000],w[1000];
    int f[1000]={0};
    scanf("%d%d",&n,&v);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&w[i],&c[i]);
    for(int i=1;i<=n;i++)
    for(int j=v;j>=c[i];j--)
    f[j]=max(f[j],f[j-c[i]]+w[i]);
    printf("%d",f[v]);

    return 0;
    }

  • 0
    @ 2016-04-21 21:38:04

    var
    a,t:array[1..100]of integer;
    f:array[0..100,0..1000]of longint;
    mt,n,i,j:integer;
    begin
    readln(n);
    readln(mt);
    for i:=1 to n do
    readln(a[i],t[i]);
    fillchar(f,sizeof(f),0);
    for i:=1 to n do
    for j:=1 to mt do
    begin
    f[i,j]:=f[i-1,j];
    if (j>=t[i])and(f[i-1,j-t[i]]+a[i]>f[i,j])then
    f[i,j]:=f[i-1,j-t[i]]+a[i];
    end;
    writeln(f[n,mt]);
    end.

  • 0
    @ 2016-04-14 19:55:37

    #include<cstdio>
    int f[1000],n,m,v,p;
    int main()
    {
    scanf("%d%d",&n,&m);
    while(n--)
    {
    scanf("%d%d",&v,&p);
    for(int i=m;i>=p;--i)
    f[i]=std::max(f[i],f[i-p]+v);
    }
    printf("%d",f[m]);
    return 0;
    }

  • 0
    @ 2016-03-29 13:02:55

    记忆化搜索(通俗易通啊)

    #include <iostream>

    #include <fstream>

    using namespace std;

    ifstream fin("fin.in");

    ofstream fout("fout.out");

    int n,t,f[110],h[110],g[1100][110]={0};

    void Input()

    {

    cin>>n>>t;

    for(int i=1;i<=n;i++) cin>>f[i]>>h[i];

    }
    int algorithm(int y,int x)

    {

    // fout<<y<<" "<<x<<"\n";

    if(x==0||y==0) return 0;

    if(g[y][x]) return g[y][x];

    int a=0,b;

    if(y>=h[x]) a=algorithm(y-h[x],x-1)+f[x];

    b=algorithm(y,x-1);

    if(a>b) b=a;

    g[y][x]=b;

    return g[y][x];

    }

    int main()

    {

    Input(); //输入

    // for(int i=1;i<=10;i++)

    // for(int j=1;j<=10;j++)

    //fout<<g[i][j];

    int m=algorithm(t,n); //算法

    cout<<m;

    }

    递推(总算弄懂了,汗)

    #include <iostream>

    #include <fstream>

    using namespace std;

    ifstream fin("fin.in");

    ofstream fout("fout.out");

    int n,t,f[110],g[110],h[1010];

    void Input()

    {

    cin>>n>>t;

    for(int i=1;i<=n;i++) cin>>f[i]>>g[i];

    }

    int main()

    {

    Input(); //输入

    for(int i=1;i<=n;i++){

    for(int j=t;j>=g[i];j--)

    if(h[j]<h[j-g[i]]+f[i]) h[j]=h[j-g[i]]+f[i];

    }
    cout<<h[t];

    }

  • 0
    @ 2016-03-15 17:42:59

    求大神指点

  • 0
    @ 2016-03-15 17:42:42

    这哪里错了
    var i,j,k,m,n,l,x,y:longint;
    a,b:array[0..1000]of longint;
    c:array[0..100,0..1000]of longint;
    begin
    readln(n);
    readln(m);
    for i:=1 to n do
    read(a[i],b[i]);
    for i:=1 to n do
    begin
    for j:=1 to m do
    begin
    if b[i]>j then
    c[i,j]:=c[i-1,j];
    if (b[i]=j)and(a[i]>c[i,j]) then
    c[i,j]:=a[i];
    if (b[i]<j)and(c[i-1,j]>c[i-1,j-b[i]]+a[i]) then
    c[i,j]:=c[i-1,j];
    if (b[i]<j)and(c[i-1,j]<=c[i-1,j-b[i]]+a[i]) then
    c[i,j]:=c[i-1,j-b[i]]+a[i];
    end;
    end;
    write(c[n,m]);
    end.

  • 0
    @ 2015-12-14 00:14:38

    #include<iostream>
    using namespace std;
    const int max_place=1000;
    const int max_time=1000;
    int totaltime;
    int totalplace;
    int like[max_place];
    int timetake[max_place];
    int maxlike[max_time][max_place];
    int p,t,minitime;

    int max(int a,int b)
    {
    if(a>=b) return a;
    else return b;
    }

    int mintime(int time[],int p)
    {
    int i,min=10000;
    for(i=0;i<p;i++)
    {
    if(time[i]<=min) min=time[i];

    }
    return min;
    }

    int GetMaxLike(int time,int placeNum)
    {
    int retMaxLike;
    int minitime=mintime(timetake,p);
    if(maxlike[time][placeNum]!=-1)
    {
    retMaxLike=maxlike[time][placeNum];
    }
    else if(placeNum==0)
    {
    if(time>=minitime)
    retMaxLike=like[placeNum];
    else
    retMaxLike=0;
    }
    else if(time>=timetake[placeNum])
    {
    retMaxLike=max(GetMaxLike(time-timetake[placeNum],placeNum-1)+like[placeNum],GetMaxLike(time,placeNum-1));
    }
    else
    {
    retMaxLike=GetMaxLike(time,placeNum-1);
    }
    maxlike[time][placeNum] =retMaxLike ;
    return retMaxLike;

    }
    int main()
    {
    for(int i=0; i<max_time; i++)
    for(int j=0; j<max_place; j++)
    maxlike[i][j] = -1;

    cin>>p>>t;
    for(int i=0;i<p;i++)
    {
    cin>>like[i];
    cin>>timetake[i];
    }
    cout<<GetMaxLike(t,p-1)<<endl;

    }
    不知道哪儿错了,求指教~~

  • 0
    @ 2015-10-29 18:28:25

    麻烦大神给指导!!!竟然拼写错误!我用pascal代入测试数据是过了的!

    uses math;
    var n,m w,v,i,j:longint;
    dp:array[0..1000,0..1000] of longint;
    begin
    readln(n);
    readln(m);
    for i:= 1 to n do
    begin
    readln(v,w);
    for j:= w to m do
    dp[i,j]:=max(dp[i-1,j],dp[i-1,j-w]+v);
    for j:= 0 to w-1 do
    dp[i,j]:=dp[i-1,j];
    end;
    writeln(dp[n,m]);
    end.

  • 0
    @ 2015-10-22 14:24:55

    #include <cstdio>

    using namespace std;

    inline int max(int a,int b) {
    return a>b?a:b;
    }

    int main(void) {
    int n=0,v=0;
    scanf("%d %d",&n,&v);
    int w[n],c[n];
    for (int i=0;i<n;++i)
    scanf("%d %d",w+i,c+i);
    int f[v+1];
    for (int i=0;i<=v;++i)
    f[i]=0;
    for (int i=0;i<n;++i)
    for (int j=v;j>=0;--j)
    if (j>=c[i])
    f[j]=max(f[j],f[j-c[i]]+w[i]);
    int ans=0;
    for (int i=0;i<v+1;++i)
    if (f[i]>ans)
    ans=f[i];
    printf("%d\n",ans);
    return 0;
    }

    QwQ我好菜

  • 0
    @ 2015-10-11 20:09:15

    评测状态 Accepted
    题目 P1025 小飞侠的游园方案
    递交时间 2015-10-09 18:17:59
    代码语言 Pascal
    评测机 VijosEx
    消耗时间 15 ms
    消耗内存 904 KiB
    评测时间 2015-10-09 18:18:01
    评测结果
    编译成功

    Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
    Copyright (c) 1993-2014 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    Linking foo.exe
    16 lines compiled, 0.0 sec , 28176 bytes code, 1628 bytes data
    测试数据 #0: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 904 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 900 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 900 KiB, score = 10
    Accepted, time = 15 ms, mem = 904 KiB, score = 100
    代码
    var n,t,i,j:longint;
    w,v:array[1..10000]of longint;
    f:array[0..100000]of longint;
    function max(x,y:longint):longint;
    begin
    if x>y then max:=x else max:=y;
    end;
    begin
    readln(n);
    readln(t);
    fillchar(f,sizeof(f),0);
    for i:=1 to n do readln(w[i],v[i]);
    for i:=1 to n do
    for j:=t downto v[i] do
    if f[j]<f[j-v[i]]+w[i] then f[j]:=f[j-v[i]]+w[i];
    writeln(f[t]);
    end.

    我要狂刷我的动态规划!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

信息

ID
1025
难度
4
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
9833
已通过
4001
通过率
41%
被复制
10
上传者