题解

85 条题解

  • 3
    @ 2020-08-29 11:19:45

    01背包变例

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

    }
    for(int i=1;i<=c;i++){
    if(a[i]>=n&&p<c-i)p=c-i;
    }
    if(p==-1)cout<<"Impossible";
    else cout<<p;
    return 0;
    }

  • 2
    @ 2020-05-24 12:24:35

    普及难度

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int dp[10005];
    int main(){
        int v,n,c,i,k,m,j,cmax=-1;
        scanf("%d%d%d",&v,&n,&c);
        for(i=1;i<=n;i++){
            scanf("%d%d",&k,&m);
            for(j=c;j>=m;j--)dp[j]=max(dp[j],dp[j-m]+k);
        }
        for(j=0;j<=c;j++)if(dp[j]>=v)cmax=max(cmax,c-j);
        dp[c]<v?printf("Impossible"):printf("%d",cmax);
        return 0;
    }
    
  • 1
    @ 2019-08-01 15:11:02

    最开始以为是对V做DP,后来想想,好像填超过V也算填平啊。
    之后改为对C做DP求耗费C时能填最大的V是多少,然后贪心找第一个能超过海容量的C。

    #include <iostream>
    
    using namespace std;
    
    int mv,n,mc;
    int dp[100000]={0};
    
    int main()
    {
        cin>>mv>>n>>mc;
        int i,v,c;
        while(n>0)
        {
            n--;
            cin>>v>>c;
            for(i=mc;i>=c;i--)
            {
                dp[i]=max(dp[i],dp[i-c]+v);
            }
        }
        for(i=0;i<=mc;i++)
        {
            if(dp[i]>=mv)
            {
                cout<<mc-i<<endl;
                return 0;
            }
        }
        cout<<"Impossible"<<endl;
        return 0;
    }
    
  • 1
    @ 2017-04-17 20:34:48
    //p1625
    #include<iostream>
    using namespace std;
    
    int v,n,c,q[10001],p[10001],f[10001];
    
    int main()
    {
        int i,j;
        cin>>v>>n>>c;
        for (i=1;i<=n;i++) cin>>q[i]>>p[i];
        for (i=1;i<=n;i++)
            for (j=c;j>=p[i];j--) 
                f[j]=f[j-p[i]]+q[i]>f[j]?f[j-p[i]]+q[i]:f[j];
        for (j=0;j<=c;j++)
            if (f[j]>=v)
            {
                cout<<c-j<<endl;
                return 0;
            }
        cout<<"Impossible"<<endl;
        return 0;
    }
    
    
  • 0
    @ 2021-02-02 23:05:50

    /*

    /
    #define method_1
    #ifdef method_1
    /

    /
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<cstring>
    #include<cstdlib>
    #include<iomanip>
    #include<ctime>
    #include<string>
    #include<bitset>
    #define D(x) cout<<#x<<" = "<<x<<" "
    #define E cout<<endl
    using namespace std;
    typedef long long ll;
    typedef pair<int,int>pii;
    const int maxn=10000+5;
    const int maxc=10000+5;
    const int INF=0x3f3f3f3f;
    //f[j]表示背包已用容量为j的最大体积
    int V,n,C;
    int v[maxn],c[maxn];
    int f[maxc];
    void dp(){
    for(int i=1;i<=n;i++){
    for(int j=C;j>=c[i];j--){
    f[j]=max(f[j],f[j-c[i]]+v[i]);
    }
    }
    for(int i=0;i<=C;i++){
    if(f[i]>=V){
    printf("%d",C-i);
    return;
    }
    }
    printf("Impossible");
    }
    int main() {
    // ios::sync_with_stdio(false);
    //freopen("精卫填海.in","r",stdin);
    scanf("%d%d%d",&V,&n,&C);
    for(int i=1;i<=n;i++){
    scanf("%d%d",&v[i],&c[i]);
    }
    dp();
    return 0;
    }
    #endif
    #ifdef method_2
    /

    */

    #endif
    #ifdef method_3
    /*

    */

    #endif

  • 0
    @ 2017-08-07 18:22:40

    心酸 突然发现超过v也可:(

    #include <iostream>
    using namespace std;
    int k[10000],m[100000];
    int dp[10000];
    int main(void){
        int v,n,c;
        cin>>v>>n>>c;
        for(int i=0;i<n;i++){
            cin>>k[i]>>m[i];
        }
        for(int i=0;i<n;i++){
            for(int j=v;j>=m[i];j--){
                dp[j]=max(dp[j],dp[j-m[i]]+k[i]);
            }
        }
        for(int i=0;i<=c;i++){
            if(dp[i]>=v) {
                cout << c - i<<endl;
                exit(0);
            }
        }
        cout<<"Impossible"<<endl;
    }
    
  • 0
    @ 2017-06-09 16:06:30
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <limits>
    #include <string>
    #include <vector>
    #include <deque>
    using namespace std;
    
    int n,m,c;
    vector<int> v;
    vector<int> w;
    vector<int> f;
    
    void c_v_1()
    {
        v.resize(0);
        w.resize(0);
        f.resize(0);
    }
    
    int main()
    {
        while (~scanf("%d%d%d",&m,&n,&c))
        {
            bool b=0;
            c_v_1();
            v.resize(n+1,0);
            w.resize(n+1,0);
            f.resize(c+1,0);
            for (int i=1;i<=n;i++)
            {
                scanf("%d%d",&v[i],&w[i]);
                for (int j=c;j>=w[i];j--)
                    f[j]=max(f[j],f[j-w[i]]+v[i]);
            }
            for (int i=0;i<=c;i++)
                if (f[i]>=m)
                {
                    printf("%d\n",c-i);
                    b=1;
                    break;
                }
            if (b==0)
                printf("Impossible\n");
        }
    }
    
    • @ 2017-06-09 16:08:55
              for (int i=0;i<=c;i++)
                  if (f[i]>=m)
                  {
                      printf("%d\n",c-i);
                      b=1;
                      break;//都怪你
                  }
      
  • 0
    @ 2017-05-20 20:35:05

    这道题是一个比较普通的01背包

    如果f【m】还是小于要填的体积的话直接Impossible

    否则从1到m开始扫数组,因为f数组表示的是在还有体力i下能填的最大体积

    所以如果遇到一个f【i】>=要填的体积就直接输出体力m-i
    #include<iostream>
    #include<cstdio>
    #include<cctype>
    template <typename T>
    T read(){
    T num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
    if(ch=='-') f=-1;
    ch=getchar();
    }
    while(isdigit(ch)){
    num=num*10+ch-'0';
    ch=getchar();
    }
    return num*f;
    }
    #define read() read<long long>()

    int w[20000];
    int c[20000];
    int f[20000];
    int main()
    {
    int q=read(),n=read(),m=read();
    for(int i=1;i<=n;++i){
    c[i]=read();
    w[i]=read();
    }
    for(int i=1;i<=n;++i)
    for(int v=m;v>=w[i];--v)
    if(f[v]<f[v-w[i]]+c[i]) f[v]=f[v-w[i]]+c[i];
    if(f[m]<q){
    printf("Impossible");
    return 0;
    }
    else
    for(int i=1;i<=m;++i)
    if(f[i]>=q){
    printf("%d",m-i);
    return 0;
    }
    return 0;
    }

  • 0
    @ 2017-03-01 09:02:15

    #include<bits/stdc++.h>
    #define ll long long
    #define st string
    using namespace std;
    struct he{
    int a,b;
    }a[10005];
    int f[10005];
    int main()
    {
    int v,n,c;
    cin>>v>>n>>c;
    for(int i=0;i<=n;i++) f[i]=1;
    for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b;
    for(int i=1;i<=n;i++){
    for(int j=c;j>=a[i].b;j--) if(j-a[i].b>=0) {
    f[j]=max(f[j],f[j-a[i].b]+a[i].a);
    }
    }
    for(int i=0;i<=c;i++) {
    if(f[i]>=v) {
    cout<<c-i<<endl;
    return 0;
    }
    }
    cout<<"Impossible"<<endl;
    return 0;
    }

  • 0
    @ 2012-11-07 19:38:01

    编译通过...

    ├ 测试数据 01:答案正确... (0ms, 832KB)

    ├ 测试数据 02:答案正确... (0ms, 832KB)

    ├ 测试数据 03:答案正确... (139ms, 832KB)

    ├ 测试数据 04:答案正确... (27ms, 832KB)

    ├ 测试数据 05:答案正确... (124ms, 832KB)

    ├ 测试数据 06:答案正确... (153ms, 832KB)

    ├ 测试数据 07:答案正确... (209ms, 832KB)

    ├ 测试数据 08:答案正确... (152ms, 832KB)

    ├ 测试数据 09:答案正确... (252ms, 832KB)

    ├ 测试数据 10:答案正确... (283ms, 832KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 1344ms / 832KB

    0/1背包问题,朴素就可以了

  • 0
    @ 2012-08-20 09:14:32

         我的题意啊,我的AC率啊.....

         不是填平吗,石头体积多出来不会伤着我们的脚吗?

  • 0
    @ 2012-07-25 11:04:46

    内存泄露到底咋回事?????

  • 0
    @ 2010-04-08 21:37:44

    终于过了 555555

    #include

    #include

    long f[500000]={0};

    long a[500000],b[500000];

    long n,v,t1;

    main()

    {scanf("%d %d %d",&v,&n,&t1);

    int i,j,k,l;

    for(i=1;i

  • 0
    @ 2010-03-12 20:16:26

    此题几乎就是纯裸的0/1背包,

    背包容量为c,做完一次经典的

    for i:=1 to n do

    for j:=c downto v[i] do

    f[j]:=max(f[j],f[j-v[i]]+w[i]);

    后从低到高for i:=0 to c扫一遍发现 f[i]>=v就输出。

    for i:=0 to c do

    if f[i]>=vv then

    begin

    writeln(c-i);

    halt;

    end;

    writeln('Impossible');

    end.

  • 0
    @ 2009-11-09 23:16:23

    失误了...居然用了INTEGER....中间结果会超过10000的...挖卡卡

  • 0
    @ 2009-11-08 12:46:52

    给点面子用C++做 居然800+ms ..

  • 0
    @ 2009-11-07 18:12:27

    悲剧啊。。。如此简单的题。。。。WA

  • 0
    @ 2009-11-07 15:51:01

    两种方法

    第一种-原始背包;时间空间由于本题的特殊性都较大。

    #include

    #include

    #define max(a,b) ( (a)>(b)?(a):(b) )

    #define min(a,b) ( (a)

  • 0
    @ 2009-11-06 21:38:41

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 56ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 166ms

    ├ 测试数据 10:答案正确... 197ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:419ms

    没MS........

    {Rp+++++++++++++++++++++++++}

    var

    v,n,c,i,o,j,p:longint;

    a,b:array[1..10000] of longint;

    f:array[0..10000] of longint;

    begin

    readln(v,n,c);

    for i:=1 to n do

    readln(a[i],b[i]);

    for i:=1 to n do

    for j:=c downto b[i] do

    if f[j]

  • 0
    @ 2009-11-04 22:17:29

    简单的背包。 WA了7次。。。 轻敌了...

    注意范围。我刚开始用f表示前i个物品搬体积为j的石头所用的体力。然后发现9个点都差一点,最后一个点只差了1。然后读题解,发现应该在体积大于v的f[n,j](j>v)中找,结果要累加一下石头的体积,结果还是爆了。

    后来发现,用f表示前i个物品体力为j时最多能搬多少体积的石头。然后从0到c找一下,有没有大于v的情况,有就输出。

    这告诫我们,要注意阶段的划分,注意范围...

    最后默哀一下我的AC率...

信息

ID
1625
难度
5
分类
动态规划 | 背包 点击显示
标签
递交数
3733
已通过
1354
通过率
36%
被复制
12
上传者