16 条题解

  • 0
    @ 2019-07-11 21:42:27

    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>

    using namespace std;

    int n;
    float f[5005];

    int main(int argc, const char *argv[])
    {
    scanf("%d", &n);
    for (int i = 1; i <= n * 5; ++i)
    f[i] = 100001;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
    float t;
    int v;
    scanf("%f %d", &t, &v);
    for (int j = n * 5; j >= v; --j)
    {
    f[j] = min(f[j], f[j - v] + t);
    if (f[j] <= 100.00000 && j > ans)
    ans = j;
    }
    }
    printf("%d\n", ans);
    return 0;
    }

  • 0
    @ 2015-08-19 18:32:01

    float F[5001];除了F[0]其他初始化为INF.
    费用和权值位置相反后还是01背包问题,核心代码:

    for(i=1;i<=n;i++)
    {
    scanf("%f%d",&v,&w); sum+=w;
    for(j=sum;j>=w;j--) F[j]=minf(F[j],F[j-w]+v);
    //更新获得权值j所花的最少时间F[j]。(v是费用,w是权值)
    }
    最后扫一遍找答案。
    顺便说个浮点数判断相等问题。

    double a,b,c;//float精度太小,我电脑上用double才运行正确
    a=100.0;
    b=100.0+1e-5;//系统可判断正确
    c=100.0+1e-6;//系统可判断错误
    由于浮点数的误差,系统会判断a!=b,a==c.
    如果遇到6位小数以上(包括6位)判断相等的情况,需要用<p>(a-b<1e-9 && a-b>-1e-9)<p>(1e-10……也可)。
    然而本题忽略了这个问题也AC了。
    所以我干脆也用float,6、7位精度也够了。
    然后扫一遍找答案
    for(i=1;i<=5000;i++)
    //if(F[i]-100.0<1e-9 && F[i]-100.0>-1e-9 && i>=ans) ans=i; //double F[i]
    if(F[i]<=100.0 && i>=ans) ans=i;
    printf("%d",ans);

  • 0
    @ 2015-08-14 12:05:21

    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>

    using namespace std;

    int n;
    float f[5005];

    int main(int argc, const char *argv[])
    {
    scanf("%d", &n);
    for (int i = 1; i <= n * 5; ++i)
    f[i] = 100001;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
    float t;
    int v;
    scanf("%f %d", &t, &v);
    for (int j = n * 5; j >= v; --j)
    {
    f[j] = min(f[j], f[j - v] + t);
    if (f[j] <= 100.00000 && j > ans)
    ans = j;
    }
    }
    printf("%d\n", ans);
    return 0;
    }

  • 0
    @ 2015-07-31 21:41:15

    P1836HYS与七夕节大作战Accepted
    记录信息
    评测状态 Accepted
    题目 P1836 HYS与七夕节大作战
    递交时间 2015-07-31 21:40:25
    代码语言 C++
    评测机 VijosEx
    消耗时间 63 ms
    消耗内存 576 KiB
    评测时间 2015-07-31 21:40:28
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 572 KiB, score = 10
    测试数据 #1: Accepted, time = 9 ms, mem = 572 KiB, score = 10
    测试数据 #2: Accepted, time = 4 ms, mem = 568 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 572 KiB, score = 10
    测试数据 #4: Accepted, time = 17 ms, mem = 572 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #6: Accepted, time = 1 ms, mem = 572 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #8: Accepted, time = 1 ms, mem = 568 KiB, score = 10
    测试数据 #9: Accepted, time = 1 ms, mem = 572 KiB, score = 10
    Accepted, time = 63 ms, mem = 576 KiB, score = 100

    #include <iostream>
    #include <stdio.h>
    using namespace std;
    int time[10010];
    int gf[1010][2];
    int main()
    {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    double a;
    int b;
    scanf("%lf%d",&a,&b);
    int c=a*100;
    gf[i][0]=c;
    gf[i][1]=b;
    }
    for(int i=1;i<=n;i++)
    for(int j=10000;j>=gf[i][0];j--)
    time[j]=max(time[j],time[j-gf[i][0]]+gf[i][1]);
    printf("%d",time[10000]);
    }

    • @ 2016-10-13 20:11:35

      所以说一样的做法为啥我wa了

    • @ 2016-10-13 20:14:50

      懂了 我看到 题目要求保留五位小数 实际不用

  • 0
    @ 2015-03-18 17:41:58

    #include<stdio.h>
    #include<string.h>
    int dp[1001][10001],p[1001];
    int t[1001];
    int max(int a,int b)
    {
    if(a>b)return a;
    else return b;
    }
    int main()
    {
    int i,j,n;
    double m;
    scanf("%d",&n);
    memset(t,0,sizeof(t));
    for(i=0;i<n;i++)
    {
    scanf("%lf%d",&m,&p[i]);
    t[i]=(int)(m*100);
    }
    for(i=n-1;i>=0;i--)
    {
    for(j=0;j<=10000;j++)
    {
    dp[i][j]=(i==n-1?0:dp[i+1][j]);
    if(j>=t[i])
    {
    //printf("get\n");
    dp[i][j]=max(dp[i][j],dp[i+1][j-t[i]]+p[i]);
    //printf("%d\n",dp[i][j]);
    }
    }
    }
    printf("%d",dp[0][10000]);
    return 0;
    }
    没搞懂输出为啥要是五位精度的小数。。。。

  • 0
    @ 2014-11-03 11:22:46

    代码
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;

    struct Girl
    {
    double im;
    int v;
    }g[1005];

    int n,sum[1005];
    double f[5005];

    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%lf%d",&g[i].im,&g[i].v);
    sum[i]+=sum[i-1]+g[i].v;
    }
    memset(f,0x7777777f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
    for(int j=sum[i];j>=g[i].v;j--)
    f[j]=min(f[j],f[j-g[i].v]+g[i].im);
    for(int i=sum[n];i>=0;i--)
    if(f[i]<=100)
    {
    printf("%d\n",i);
    break;
    }
    return 0;
    }

  • 0
    @ 2014-02-13 14:39:22

    这种题懒得往blog上发了。。。
    很容易想到倒着算。。
    代码
    #include <iostream>
    using namespace std;
    #define INF 1000000000
    #define SIZE 1001
    int n,sum,get[SIZE];
    double spe[SIZE],opt[SIZE*5];
    void init()
    {
    cin>>n;
    for (int i = 1; i <= n; i++)
    {
    cin>>spe[i]>>get[i];
    sum += get[i];
    }
    }
    void work()
    {
    for (int i = 1; i <= sum; i++)
    {
    opt[i] = INF;
    }
    sum = 0;
    for (int i = 1; i <= n; i++)
    {
    for (int j = sum; j >= 0; j--)
    {
    opt[j+get[i]] = min(opt[j+get[i]],opt[j] + spe[i]);
    }
    sum += get[i];
    }
    }
    int print()
    {
    for (int i = sum; i >= 0; i--)
    {
    if ( opt[i] < 100 )
    {
    cout<<i;
    return 0;
    }
    }
    }
    int main()
    {
    init();
    work();
    print();
    return 0;
    }

  • 0
    @ 2014-01-01 12:03:01

    Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

  • 0
    @ 2013-11-08 08:20:55

    var
    f,b:array[0..6000]of real;
    a:array[0..6000]of longint;
    c,d,e,g,h,i,j,k,l,m,n:longint;

    function min(a,b:real):real;
    begin if a<b then exit(a);exit(b);end;

    begin
    read(n);
    for i:=1 to n do begin read(b[i],a[i]);m:=m+a[i];end;
    fillchar(f,sizeof(f),127);
    f[0]:=0;
    for i:=1 to n do
    for j:=m downto a[i] do
    f[j]:=min(f[j],f[j-a[i]]+b[i]);
    for i:=1 to m do if f[i]<=100.00000001 then h:=i;
    writeln(h);
    end.
    表示真的简单……

    • @ 2015-01-15 17:17:55

      怪不得我一直运行不了,忘记把边界0给弄成0了,谢谢你程序的提醒。

  • 0
    @ 2013-11-03 20:38:15

    反正楼下首届花撸大赛冠军LCS提供思路!
    今天刷了一大堆背包,思路都定死了,没有反应到用重要值当做下标做背包。
    仔细即可!
    dxe

    • @ 2015-01-15 17:18:42

      新手,同没有反应到。我想这题会让我以后遇到这种题目会记忆犹新。感谢点拨

  • 0
    @ 2013-09-29 21:13:26

    很容易想到反着写,正这写考虑下标不可以,虽然可以将输入的数据A【I】成100000变成整数,但时间上不允许。注意输出按样例的来就可以了,别保留啊!

  • 0
    @ 2013-09-12 20:51:48

    无聊的来SOFA一下题解。
    由于v实在很小 所以我们可以把背包反过来做
    f[i]表示价值为i的选择方案所需要的最少的代价,然后就是简单的O1背包啦~

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 492 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 492 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 488 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 492 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 492 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 488 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 492 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 488 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 492 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 488 KiB, score = 10
    Accepted, time = 45 ms, mem = 492 KiB, score = 100
    #include <cstdio>
    #include <algorithm>
    #include <cstring>

    using namespace std;

    #define MAXN 1001
    #define MAXM 5001
    #define inf 1000000000

    double f[MAXM];
    double t[MAXN];
    int v[MAXN];

    int n,sum=0;

    int main(){
    scanf("%d",&n);
    for (int i=0;i++<n;){
    scanf("%lf%d",&t[i],&v[i]);
    sum+=v[i];
    }
    f[0]=0;
    for (int i=0;i++<sum;){
    f[i]=inf;
    }
    for (int i=0;i++<n;){
    for (int j=sum;j>=v[i];j--){
    f[j]=min(f[j],f[j-v[i]]+t[i]);
    }
    }
    int ans=0;
    for (int i=0;i++<sum;){
    if (f[i]<=100){
    ans=max(ans,i);
    }
    }
    printf("%d\n",ans);
    return 0;
    }

  • -1
    @ 2017-03-13 18:29:58

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

  • -1
    @ 2017-01-21 12:16:36

    #include <cstdio>
    #include <algorithm>
    #define oo 1000000000
    using namespace std;

    struct node1
    {
    int v;
    double t;
    }a[1001];

    int main()
    {
    int n,ans=0,v=0;
    double f[5001];
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
    scanf("%lf%d",&a[i].t,&a[i].v);
    v+=a[i].v;
    }
    f[0]=0;
    for (int i=1;i<=v;i++)
    f[i]=oo;
    for (int i=1;i<=n;i++)
    for (int j=v;j>=a[i].v;j--)
    {
    f[j]=min(f[j],f[j-a[i].v]+a[i].t);
    if (f[j]<=100)
    ans=max(ans,j);
    }
    printf("%d\n",ans);
    }

  • -1
    @ 2016-09-10 10:06:05

    简直爽
    ```C++
    #include <set>
    #include <map>
    #include <list>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <cctype>
    #include <cstdio>
    #include <string>
    #include <vector>
    #include <cassert>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #define maxn (1000 + 20)
    #define inf 0x3f3f3f3f
    #define pi acos(-1.0)
    using namespace std;
    typedef long long int LLI;

    double t[maxn];
    int v[maxn];
    double dp[10000000 + 50];

    int main() {
    // freopen("in.txt","r",stdin);
    // freopen("out1.txt","w",stdout);
    int n,sum = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++)
    scanf("%lf%d",&t[i],&v[i]),sum += v[i];
    for(int i = 0;i <= sum;i ++) dp[i] = 1000.0;
    dp[0] = 0;
    int re = 0;
    for(int i = 1; i <= n; i ++) {
    for(int j = sum; j >= v[i]; j --) {
    dp[j] = min(dp[j],dp[j - v[i]] + t[i]);
    if(dp[j] < 100.0) re = max(re,j);
    }
    }
    printf("%d\n",re);
    return 0;
    }
    ```

  • -1
    @ 2016-08-09 09:06:44

    此题有毒。一开始竟然差点被坑了。还好反应过来了。
    注意逆向思维~状态描述楼下都已经有了~
    直接上代码吧~
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <iomanip>
    #include <cstdlib>
    using namespace std;

    const int INF=0x7fff;
    double f[5000];
    int n;
    double T=100.0;

    int main()
    {
    double t;
    int w;
    cin>>n;
    for(int i=1;i<=5*n;i++)
    f[i]=INF;
    for(int i=1;i<=n;i++)
    {
    cin>>t>>w;
    for(int j=n;j>=w;j--)
    f[j]=min(f[j],f[j-w]+t);
    }
    int ans=0;
    for(int i=n;i>=0;i--)
    if(f[i]<=100)
    { cout<<i<<endl;
    break;}
    return 0;
    }

  • 1

信息

ID
1836
难度
5
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
771
已通过
291
通过率
38%
被复制
1
上传者