200 条题解

  • 12
    @ 2017-05-07 22:28:16
    /*
    此题很明显是经典的0/1背包问题,对于每张牌都有选或不选的办法
    则做法已经很明确
    1.dfs深搜枚举所有情况,O(2^n)复杂度过高
    2.动态规划
    基础思路:设bool数组f[i][j]为选到第i张牌的时候重量为j的可能性
    但是注意,这里要求要判断多个解的情况,所以不能光用bool数组了
    同时我们考虑0/1背包的暗箱思想+一维优化,则可以得出这样的状态描述
        f[j]表示某层容量为j时的情况
        f[j]==0则有达不到,f[j]==1则有答案,f[j]==-1则说明有多解
    用f[j]=-1表示多解而不用2什么的是为了更好的方便输出答案(多解无解都可以直接输出f[sum])
    则根据以上状态有状态转移方程
    f[j]=
    {
        1,f[j-a[i]]==0;
        -1,f[j-a[i]]>0;
    }
    每次j从sum倒推到a[i]即可,每次递推都是建立在上一次基础上
    这是0/1背包的基本功了
    容易知道如果某个f[j]==-1了,那么一直到最后不管推多少次都还是-1
    所以容易得到该算法的正确性
    打印解的时候我们要打印的应该是装满sumw-w的方案
    这里可以dfs也可以直接迭代
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=105;
    const int MAXW=100005;
    int f[MAXW],pre[MAXW];
    int ans[MAXN];
    int a[MAXN];
    int n,w,sumw;
    
    void init()
    {
        scanf("%d",&w);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sumw+=a[i];
        }
    }
    
    void DP()
    {
        f[0]=1;
        for(int i=1;i<=n;i++)
            for(int j=sumw;j>=a[i];j--)
                if(f[j-a[i]]>0)
                {
                    if(f[j]>0)
                        f[j]=-1;
                    else    if(f[j]==0)
                    {
                        f[j]=1;
                        pre[j]=i;
                    }
                }
        f[0]=0;//会有w=0的点
    }
    
    void print_ans()
    {
        w=sumw-w;
        if(f[w]<=0)
            printf("%d\n",f[w]);
        else
        {
            int cnt=0,cur=w;
            while(cur)
            {
                ans[++cnt]=pre[cur];
                cur-=a[pre[cur]];
            }
            for(int i=cnt;i>=1;i--)
                printf("%d ",ans[i]);
            printf("\n");
        }
    }
    
    int main()
    {
        init();
        DP();
        print_ans();
    }
         
    
  • 2
    @ 2018-07-29 12:39:19

    01背包+还原决策方案

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define pos(x,y) (x+(y)*n)
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7777777;
    const double eps=1e-8;
    
    int w;
    int n;
    int a[105];
    int f[105][100*1000+1];
    int p[105][100*1000+1];
    bool remain[105];
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        scanf("%d %d",&w,&n);
        FOR(i,n) scanf("%d",&a[i]);
        f[0][0]=1;
        FOR(i,n) REP(j,0,w) 
        {
            f[i][j]=f[i-1][j]+(j>=a[i]?f[i-1][j-a[i]]:0);
        }
        if (f[n][w]==0) {
            cout<<0<<endl;
            return 0;
        } else if (f[n][w]>1) {
            cout<<-1<<endl;
            return 0;
        } else {
            int x=n,y=w;
            while (y) {
                if (f[x-1][y]==0) {
                    remain[x]=1;
                    y-=a[x];
                    x--;
                } else x--;
            }
        }
        FOR(i,n) if (!remain[i]) cout<<i<<" ";
        cout<<endl;
        return 0;
    }
    
  • 1
    @ 2020-07-26 22:05:14

    dp统计方案数,再判断方案数,若为1,再dfs搜方案即可。

    #include<bits/stdc++.h>
    using namespace std;
    int n,yu,v;
    int a[105];
    int dp[100005];
    int ans[105],k;
    bool ok;
    void dfs(int x,int sum){
        if(sum==v){
            ok=1;
            for(int i=1;i<=k;i++)
                cout<<ans[i]<<' ';
            return;
        }
        if(ok)return;
        if(x==n+1)return;
        ans[++k]=x;
        dfs(x+1,sum+a[x]);
        k--;
        dfs(x+1,sum);
    }
    int main(){
        cin>>yu>>n;
        int sum=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum+=a[i];
        }
        v=sum-yu;
        dp[0]=1;
        for(int i=1;i<=n;i++)
        for(int j=v;j>=a[i];j--)
            dp[j]+=dp[j-a[i]];
        if(dp[v]==0){
            cout<<'0';
            return 0;
        }
        if(dp[v]>1){
            cout<<"-1";
            return 0;
        }
        dfs(1,0);
        return 0;
    }
    
  • 1
    @ 2018-06-03 14:36:58

    01背包来一发

    网上看了好些记录方法都不太喜,自己就写了个

    解法一
    Pascal
    var dp,vis:array[0..100004]of longint;
    a,put:array[0..104]of longint;
    n,i,j,v,sum,flag,tp,ok:longint;
    begin
    readln(v,n);
    for i:=0 to n-1 do
    begin
    read(a[i]);
    sum:=sum+a[i];
    end;
    v:=sum-v;
    fillchar(vis,sizeof(vis),255);
    for i:=0 to n-1 do
    for j:=v downto a[i] do
    begin
    if(dp[j-a[i]]+a[i]>dp[j])then begin
    dp[j]:=dp[j-a[i]]+a[i];
    vis[j]:=i;
    end
    else if(dp[j-a[i]]+a[i]=dp[j])and(dp[j]=j)and(j=v)then flag:=1;
    end;
    if dp[v]<>v then writeln(0)
    else if(flag=1)then writeln(-1)
    else begin
    tp:=v;
    ok:=0;
    while(vis[tp]<>-1)do
    begin
    put[ok+1]:=vis[tp]+1;
    inc(ok);
    tp:=tp-a[vis[tp]];
    end;
    for i:=ok downto 0 do
    if i<>0 then write(put[i],' ');
    end;
    end.

    解法二
    Pascal
    var f:array[0..200000]of longint;
    b:array[0..100]of longint;
    a:array[0..100]of longint;
    c:array[0..200000]of longint;
    n,v,i,j:longint;
    begin
    readln(v);
    readln(n);
    for i:=1 to n do
    readln(a[i]);
    f[0]:=1;
    for i:=1 to n do
    for j:=v downto a[i] do
    if f[j-a[i]]>0 then
    begin
    if f[j]=0 then c[j]:=i;
    f[j]:=f[j]+f[j-a[i]];
    if (j=v) and (f[j]>1) then begin writeln(-1);halt; end;
    end;
    if f[v]=0 then
    begin
    writeln(0);
    halt;
    end;
    if f[v]=1 then
    begin
    i:=v;
    while i<>0 do
    begin
    inc(b[c[i]]);
    dec(i,a[c[i]]);
    end;
    for i:=1 to n do
    if b[i]=0 then
    write(i,' ');
    end;
    end.

    最后,P党加油!

  • 1
    @ 2018-06-01 20:39:14
    **将楼上题解翻译成Pascal**
    
    此题很明显是经典的0/1背包问题,对于每张牌都有选或不选的办法
    则做法已经很明确
    1.dfs深搜枚举所有情况,O(2^n)复杂度过高
    2.动态规划
    基础思路:设bool数组f[i][j]为选到第i张牌的时候重量为j的可能性
    但是注意,这里要求要判断多个解的情况,所以不能光用bool数组了
    同时我们考虑0/1背包的暗箱思想+一维优化,则可以得出这样的状态描述
        f[j]表示某层容量为j时的情况
        f[j]==0则有达不到,f[j]==1则有答案,f[j]==-1则说明有多解
    用f[j]=-1表示多解而不用2什么的是为了更好的方便输出答案(多解无解都可以直接输出f[sum])
    则根据以上状态有状态转移方程
    f[j]=
    {
        1,f[j-a[i]]==0;
        -1,f[j-a[i]]>0;
    }
    每次j从sum倒推到a[i]即可,每次递推都是建立在上一次基础上
    这是0/1背包的基本功了
    容易知道如果某个f[j]==-1了,那么一直到最后不管推多少次都还是-1
    所以容易得到该算法的正确性
    打印解的时候我们要打印的应该是装满sumw-w的方案
    这里可以dfs也可以直接迭代
    代码如下:
    
    C++原版:
    
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=105;
    const int MAXW=100005;
    int f[MAXW],pre[MAXW];
    int ans[MAXN];
    int a[MAXN];
    int n,w,sumw;
    
    void init()
    {
        scanf("%d",&w);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sumw+=a[i];
        }
    }
    
    void DP()
    {
        f[0]=1;
        for(int i=1;i<=n;i++)
            for(int j=sumw;j>=a[i];j--)
                if(f[j-a[i]]>0)
                {
                    if(f[j]>0)
                        f[j]=-1;
                    else    if(f[j]==0)
                    {
                        f[j]=1;
                        pre[j]=i;
                    }
                }
        f[0]=0;//会有w=0的点
    }
    
    void print_ans()
    {
        w=sumw-w;
        if(f[w]<=0)
            printf("%d\n",f[w]);
        else
        {
            int cnt=0,cur=w;
            while(cur)
            {
                ans[++cnt]=pre[cur];
                cur-=a[pre[cur]];
            }
            for(int i=cnt;i>=1;i--)
                printf("%d ",ans[i]);
            printf("\n");
        }
    }
    
    int main()
    {
        init();
        DP();
        print_ans();
    }
    
    翻译成Pascal:
    
    const
      maxn=105;
      maxw=100005;
    var
      f,pre:array[0..maxw] of longint;
      ans,a:array[0..maxn] of longint;
      n,w,sumw:longint;
    procedure init;
    var
      i:longint;
    begin
      readln(w);
      readln(n);
      for i:=1 to n do
      begin
        readln(a[i]);
        sumw:=sumw+a[i];
      end;
    end;
    procedure dp;
    var
      i,j:longint;
    begin
      f[0]:=1;
      for i:=1 to n do
        for j:=sumw downto a[i] do
          if f[j-a[i]]>0 then
          begin
            if f[j]>0 then f[j]:=-1
            else
            if f[j]=0 then
            begin
              f[j]:=1;
              pre[j]:=i;
            end;
          end;
      f[0]:=0;
    end;
    procedure print_ans;
    var
      cnt,cur,i:longint;
    begin
      w:=sumw-w;
      if f[w]<=0 then writeln(f[w])
      else
      begin
        cnt:=0;cur:=w;
        while cur<>0 do
        begin
          cnt:=cnt+1;
          ans[cnt]:=pre[cur];
          cur:=cur-a[pre[cur]];
        end;
        for i:=cnt downto 1 do
          write(ans[i],' ');
        writeln;
      end;
    end;
    begin
      init;
      dp;
      print_ans;
    end.
    (yxl翻译)
    
  • 1
    @ 2017-08-16 12:57:14

    //暴力dp,空间有点大
    //f(i, j) 表示前i张牌能否取到j的重量
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<stack>
    using namespace std;

    int a[105];
    bool f[105][100010];
    stack<int> ans;

    int main()
    {
    int w, n, sum=0;
    cin>>w>>n;
    for(int i=1;i<=n;i++){ scanf("%d", &a[i]); sum+=a[i]; }
    w=sum-w;
    f[0][0]=true;
    for(int i=1;i<=n;i++){
    for(int j=sum;j>=a[i];j--)
    f[i][j]=f[i-1][j-a[i]]|f[i-1][j];
    for(int j=0;j<a[i];j++)
    f[i][j]=f[i-1][j];
    }
    if(!f[n][w]) cout<<0<<endl;
    else{
    int j=w;
    for(int i=n;i>=1;i--){
    if(j<a[i]) continue;
    if(f[i-1][j-a[i]]&&f[i-1][j]){
    cout<<-1<<endl;
    return 0;
    }
    if(f[i-1][j-a[i]]){
    ans.push(i);
    j-=a[i];
    }
    }
    while(!ans.empty()){
    cout<<ans.top()<<' ';
    ans.pop();
    }
    cout<<endl;
    }
    return 0;
    }

  • 0
    @ 2021-12-24 20:00:13

    pf吧......我毕竟蒟蒻

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
      int n;
      cin>>n;
      if(n%2==1)
      cout<<0;
      else
      cout<<-1; 
    }
    

    --------- 分割线 -----------
    ........唉,别喷我.我

  • 0
    @ 2020-05-15 22:32:24
    #include<bits/stdc++.h>
    using namespace std;
    #define MAX 2000005
    int dp[MAX],a[MAX],path[MAX],res;
    void print(int k)
    {
        if(k){
            print(k - a[path[k]]);//找到上一个质量 
            if(k == res) cout << path[k];//最后一个不输出空格 
            else cout << path[k] << " ";
        }
    }
    int main()
    {
        int total,n,sum = 0;
        cin >> total >> n;
        for(int i = 1;i <= n;i++) cin >> a[i],sum += a[i];
        res = sum - total;//res代表丢失牌总质量 
        dp[0] = 1;//dp[i]代表丢失质量为i的牌的可能数
        for(int i = 1;i <= n;i++){
            for(int j = res;j >= a[i];j--){
                dp[j] += dp[j - a[i]];
                if(dp[j] > 5) dp[j] = 2;//这里不关心方案数,为了防止数量过大需要及时缩小
                if(!path[j] && dp[j - a[i]]) path[j] = i;//path[j]代表达到重量j时需要第i张牌 
            }
        } 
        if(!dp[res]) cout << "0" << endl;
        else if(dp[res] > 1) cout << "-1" << endl;
        else print(res);
        return 0; 
    }
    
    

    就是一道0 - 1背包问题,单数这里需要记录过程,所以用到path数组,最后递归打印。

  • 0
    @ 2019-10-30 23:29:24

    三维暴力+滚动优化;

    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #define maxn 101
    using namespace std;
    inline int read()
    {
        int w=1,tmp=0;char ch=0;
        while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){tmp=(tmp<<1)+(tmp<<3)+ch-'0';ch=getchar();}
        return w*tmp;
    }
    int remain,n,f[2][100001][2],v[maxn],sum,path[101][100001];
    void shuchu(int x,int y){
        if(x==0){
            return ;
        }
        if(path[x][y]){
            shuchu(x-1,y-v[x]);
            printf("%d ",x);
        }
        else{
            shuchu(x-1,y); 
        }
    }
    int main()
    {
        //freopen("my.out","w",stdout);
        remain=read();
        n=read();
        for(int i=1;i<=n;i++){
            v[i]=read();
            sum+=v[i];
        }
        sum-=remain;
        //for(int i=0;i<=n;i++){//0表示不选,1表示选 
            //f[i][0][0]=1;
        //}
        f[0][0][0]=1;
        f[1][0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=sum;j>=1;j--){
                if((f[(i+1)%2][j][1]||f[(i+1)%2][j][0])&&(f[(i+1)%2][j-v[i]][0]||f[(i+1)%2][j-v[i]][1])&&(j==sum)){
                    printf("-1");
                    return 0;
                }
                path[i][j]=0;
                if(f[(i+1)%2][j][1]||f[(i+1)%2][j][0]){
                    f[i%2][j][0]=1;
                 }
                if(j>=v[i]){
                    if(f[(i+1)%2][j-v[i]][0]||f[(i+1)%2][j-v[i]][1]){
                        f[i%2][j][1]=1;
                        path[i][j]=1;
                    }
                }
                if(f[i%2][j][1]==1&&f[i%2][j][0]==1&&j==sum){
                    printf("-1");
                    return 0;
                }
                //printf("f[%d][%d][0]=%d\n",i,j,f[i][j][0]);
                //printf("f[%d][%d][1]=%d\n",i,j,f[i][j][1]);
            }
        }
        if(f[n%2][sum][1]){
            shuchu(n,sum);
            //printf("yes");
            return 0;
        }
        else if(f[n%2][sum][0]){
            shuchu(n,sum);
             //printf("yes");
            return 0;
        } 
        else printf("0");
    }
    
  • 0
    @ 2019-10-30 23:28:45

    其实这道题可以三维暴力+滚动优化;

    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #define maxn 101
    using namespace std;
    inline int read()
    {
        int w=1,tmp=0;char ch=0;
        while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){tmp=(tmp<<1)+(tmp<<3)+ch-'0';ch=getchar();}
        return w*tmp;
    }
    int remain,n,f[2][100001][2],v[maxn],sum,path[101][100001];
    void shuchu(int x,int y){
        if(x==0){
            return ;
        }
        if(path[x][y]){
            shuchu(x-1,y-v[x]);
            printf("%d ",x);
        }
        else{
            shuchu(x-1,y); 
        }
    }
    int main()
    {
        //freopen("my.out","w",stdout);
        remain=read();
        n=read();
        for(int i=1;i<=n;i++){
            v[i]=read();
            sum+=v[i];
        }
        sum-=remain;
        //for(int i=0;i<=n;i++){//0表示不选,1表示选 
            //f[i][0][0]=1;
        //}
        f[0][0][0]=1;
        f[1][0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=sum;j>=1;j--){
                if((f[(i+1)%2][j][1]||f[(i+1)%2][j][0])&&(f[(i+1)%2][j-v[i]][0]||f[(i+1)%2][j-v[i]][1])&&(j==sum)){
                    printf("-1");
                    return 0;
                }
                path[i][j]=0;
                if(f[(i+1)%2][j][1]||f[(i+1)%2][j][0]){
                    f[i%2][j][0]=1;
                 }
                if(j>=v[i]){
                    if(f[(i+1)%2][j-v[i]][0]||f[(i+1)%2][j-v[i]][1]){
                        f[i%2][j][1]=1;
                        path[i][j]=1;
                    }
                }
                if(f[i%2][j][1]==1&&f[i%2][j][0]==1&&j==sum){
                    printf("-1");
                    return 0;
                }
                //printf("f[%d][%d][0]=%d\n",i,j,f[i][j][0]);
                //printf("f[%d][%d][1]=%d\n",i,j,f[i][j][1]);
            }
        }
        if(f[n%2][sum][1]){
            shuchu(n,sum);
            //printf("yes");
            return 0;
        }
        else if(f[n%2][sum][0]){
            shuchu(n,sum);
             //printf("yes");
            return 0;
        } 
        else printf("0");
    }
    
  • 0
    @ 2017-04-10 12:34:48

    http://blog.csdn.net/jackypigpig/article/details/69945527

    我的方法较为暴力——

    • 相当于做一次简单的 01背包,附加操作是记下每个状态下需要用到的牌的编号(用了个bitset),当方案数大于一时就不用再理它了。最终看看方案数分类输出就行了
    • 不过这样时间和空间(特别是空间)就十分庞大 > 总耗时59ms 峰值内存2.32MiB
    
    #include <cstdio>
    #include <bitset>
    using namespace std;
    int W,N,w,s,f[100010];
    bitset <105> g[100010];
    
    int main(){
        f[0]=1;
        scanf("%d%d",&W,&N);
        for (int i=1; i<=N; i++){
            scanf("%d",&w);
            s+=w;
            for (int j=s; j>=w; j--){
                if (f[j-w]==1){
                    if (f[j]==0) f[j]=1,g[j]=g[j-w],g[j][i]=1;
                    else f[j]++;
                }
                if (f[j-w]>1) f[j]=3;
            }
        }
        if(f[W]>1) printf("-1");
        else if (f[W]==0)printf("0");
        if (f[W]==1) for (int i=1; i<=N; i++) if (!g[W][i]) printf("%d ",i);
        return 0;
    }
    
    • 其实,你也可以不用bitset记录,可以用个类似于**邻接表**的东西记下到当前状态的**路径**,输出时走一遍,也可以。
    • 这样时间和空间都明显好很多 > 总耗时22ms 峰值内存928.0KiB
    #include <cstdio>
    int W,N,s,w[105],f[100005],e[100005];
    
    int main(){
        f[0]=1;
        scanf("%d%d",&W,&N);
        for (int i=1; i<=N; i++) scanf("%d",&w[i]);
        for (int i=(s=w[N],N); i; i--,s+=w[i]){
            for (int j=s; j>=w[i]; j--) if (f[j-w[i]]){
                if (f[j-w[i]]==1) if (f[j]==0) f[j]=1,e[j]=i; else f[j]=2;
                if (f[j-w[i]]>1) f[j]=2;
            }
        }
        s-=W;
        if (f[s]==0) printf("0");
        if (f[s]==1) for (int i=s; i; i-=w[e[i]]) printf("%d ",e[i]);
        if (f[s]>1) printf("-1");
        return 0;
    }
    
  • 0
    @ 2016-06-24 21:10:27

    简单背包……
    ```c++
    #include<cstdio>
    #include<stack>
    #include<vector>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 200;

    int n,totweith,weith[maxn],num_ans=0,allweith=0;
    char info[maxn][1100];
    vector<int> ans;
    stack<int> s;

    void dp(int now,int left)
    {
    if(info[now][left]==1) return;
    if(now==n+1)
    {
    if(left!=0) return;
    stack<int> temp=s;
    while(!temp.empty())
    {
    ans.push_back(temp.top());
    temp.pop();
    }
    num_ans++;
    return;
    }
    int k=num_ans;
    if(weith[now]<=left)
    {
    s.push(now);
    dp(now+1,left-weith[now]);
    s.pop();
    }
    if(num_ans>=2) return;
    dp(now+1,left);
    if(num_ans==k) info[now][left]=1;
    }

    int main()
    {
    /*freopen("bag","r",stdin);*/
    memset(info,-1,sizeof(info));
    scanf("%d%d",&totweith,&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&weith[i]);
    allweith+=weith[i];
    }

    dp(1,allweith-totweith);
    if(num_ans==1)
    for(int i=(int)ans.size()-1;i>=0;i--)
    printf("%d ",ans[i]);
    else printf("%d",num_ans==0 ? 0 : -1);
    printf("\n");
    return 0;
    }

    /* Accepted, time = 45 ms, mem = 776 KiB, score = 100 2016年6月24日星期五 */
    ```

  • 0
    @ 2016-04-15 17:54:15

    更新记录之前的牌的时候要注意,不然会WA第四个点(#3)
    附上程序:
    #include<cstdio>
    bool b[101];
    int f[100001],l[100001],p[100001],m,n,w;
    void find(int i)
    {
    if(!i)
    return;
    find(l[i]);
    b[p[i]]=true;
    }
    int main()
    {
    scanf("%d%d",&m,&n);
    f[0]=1;
    for(int i=1;i<=n;++i)
    {
    scanf("%d",&w);
    for(int j=m;j>=w;--j)
    if(f[j-w])
    {
    f[j]+=f[j-w];
    if(f[j]==1)/*这条语句是重点这条语句是重点这条语句是重点,重要的事情说三遍*/
    l[j]=j-w,p[j]=i;
    }
    }
    if(f[m]>1)
    {puts("-1");return 0;}
    else
    if(!f[m])
    {puts("0");return 0;}
    find(m);
    for(int i=1;i<=n;++i)
    if(!b[i])
    printf("%d ",i);
    return 0;
    }

  • 0
    @ 2016-02-28 11:45:37

    简单背包,一个数组 f 记录方案数,另一个数组 g 记录从哪里转移而来,最后递归输出。两个数组都可以省略一维。(当然不省略也可以,只是空间开销比较大)。
    f[j] = f[j]+f[j-weight[i]]
    其中 i 是当前物品,j 是当前重量。记住 f 和 g 要开到100*1000那么大,我第一次就因为这个错。

    #include <stdio.h>
    #include <string.h>
    #define INF 1000000
    int weight[105];
    int f[100005];
    int g[100005];
    int print(int end){
    int begin, i;
    if(end == 0)
    return 0;
    begin = print(g[end]);
    for(i=begin+1; i<=end; i++){
    if(end-g[end] == weight[i]){
    printf("%d ", i);
    return i;
    }
    }
    }
    int main(){
    int num, totalW;
    int i, j;
    scanf("%d %d", &totalW, &num);
    totalW *= -1;
    for(i=1; i<=num; i++){
    scanf("%d", &weight[i]);
    totalW += weight[i];
    }
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    f[0] = 1;
    for(i=1; i<=num; i++){
    for(j=totalW; j>=weight[i]; j--){
    f[j] += f[j-weight[i]];
    if(f[j-weight[i]] > 0)
    g[j] = j-weight[i];
    }
    }
    if(f[totalW] > 1)
    printf("-1");
    else if(f[totalW] == 0)
    printf("0");
    else
    print(totalW);
    return 0;
    }

    • @ 2016-04-09 15:32:38

      Print函数里面的循环不应该是begin+1到n么?

  • 0
    @ 2016-01-28 22:15:06

    第一次动规过了,之后突然想试一下dfs能不能过,结果a掉6个点,2个点wa,2个tle。。。=_=,动规果然所向披靡

    • @ 2016-07-10 15:30:09

      有可能是你数组定义的太小

  • 0
    @ 2015-08-28 14:23:48

    大神们帮我看看怎么优化吧,总是超时,能给我过了的话感激不尽!
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int v[1000000]={0},n,a[101],b[101],rest,p;
    bool f[1000000][101]={0};
    void find(int x,int y,int z)
    {
    //cout<<"x="<<x<<' '<<"y="<<y<<' '<<"z="<<z<<endl;
    if(z<0){
    return;
    }
    if(z==0){
    for(int i=1;i<y;i++){
    printf("%d ",b[i]);
    }
    return;
    }
    int i;
    for(i=x;i<p;i++){
    if(v[z-a[i]]!=0){
    b[y]=i;
    z-=a[i];
    find(i+1,y+1,z);
    z+=a[i];
    }
    }
    return;
    }
    int main()
    {
    int weight,sum[101]={0},i,j;
    scanf("%d%d",&weight,&n);
    for(i=1;i<=n;i++){
    scanf("%d",&a[i]);
    sum[i]=sum[i-1]+a[i];
    }
    rest=sum[n]-weight;
    v[0]=1;
    for(j=1;j<=n;j++){
    for(i=rest;i>=1;i--){
    if(a[j]<=i&&v[i-a[j]]!=0){
    if(i==rest){
    p=j;
    }
    v[i]+=v[i-a[j]];

    }
    }

    }
    //cout<<"p="<<p<<endl;
    if(v[rest]==0){
    printf("0");
    return 0;
    }
    else if(v[rest]>1){
    printf("-1");
    return 0;
    }
    else{
    find(1,1,rest-a[p]);
    printf("%d",p);
    }
    }

  • 0
    @ 2015-08-25 06:15:03

    格式不大好,大家见谅

  • 0
    @ 2015-08-25 06:14:29

    求大神们帮我看看怎么优化,总是超时。
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int v[1000000]={0},n,a[101],b[101],rest;
    bool f[1000000][101]={0};
    void find(int x,int y,int z)
    {
    if(z<0){
    return;
    }
    if(x>n&&z==0){
    for(int i=1;i<y;i++){
    printf("%d ",b[i]);
    }
    return;
    }
    int i;
    for(i=x;i<=n;i++){
    if(v[z-a[i]]!=0){
    b[y]=i;
    z-=a[i];
    find(i+1,y+1,z);
    z+=a[i];
    }
    }
    return;
    }
    int main()
    {
    int weight,sum[101]={0},i,j;
    scanf("%d%d",&weight,&n);
    for(i=1;i<=n;i++){
    scanf("%d",&a[i]);
    sum[i]=sum[i-1]+a[i];
    }
    rest=sum[n]-weight;
    v[0]=1;
    for(j=1;j<=n;j++){
    for(i=rest;i>=1;i--){
    if(a[j]<=i&&v[i-a[j]]!=0){
    v[i]+=v[i-a[j]];

    }
    }

    }
    if(v[rest]==0){
    printf("0");
    return 0;
    }
    else if(v[rest]>1){
    printf("-1");
    return 0;
    }
    else{
    find(1,1,rest);
    }
    }

  • 0
    @ 2015-05-21 13:56:53

    01背包 输出方案有点麻烦

  • 0
    @ 2015-03-12 22:01:04

    比较暴力的两遍搜索+记忆化....
    这个数据还是比较弱的......
    第一遍DFS,就是求到达最终目标的方案总数..
    第二遍DFS,依照到达目标的方案总数做转移.....
    假设我们到达了状态(i,v),表示我们正在选择第i个牌是否存在,并且当前选取的总重为v,那么从(i,v)有且仅有一个状态转移出去(因为方案唯一,且存在方案)....
    直接判就好....

    int n,m;
    int w[105];
    int d[105][100050];
    bool used[105][100050];

    int DFS(int x,int v) //path count to end point.
    {
    if(v>m) return d[x][v]=0;
    if(x==n)
    {
    if(v==m) return d[x][v]=1;
    else return d[x][v]=0;
    }
    if(used[x][v]) return d[x][v];
    used[x][v]=true;
    return d[x][v]=min(DFS(x+1,v)+DFS(x+1,v+w[x]),2);
    }

    bool res[105];

    void SDFS(int x,int v)
    {
    if(x==n) return ;
    if(d[x+1][v]) res[x]=0,SDFS(x+1,v);
    if(d[x+1][v+w[x]]) res[x]=1,SDFS(x+1,v+w[x]);
    }

    int main()
    {
    m=getint();
    n=getint();
    for(int i=0;i<n;i++)
    w[i]=getint();

    int cnt=DFS(0,0);

    if(cnt>1) printf("-1\n");
    else if(cnt==0) printf("0\n");
    else
    {
    SDFS(0,0);
    for(int i=0;i<n;i++)
    if(!res[i]) printf("%d ",i+1);
    printf("\n");
    }

    return 0;
    }

信息

ID
1071
难度
7
分类
动态规划 | 背包 点击显示
标签
递交数
6302
已通过
1439
通过率
23%
被复制
13
上传者