/ Vijos / 题库 / 新年趣事之打牌 /

题解

200 条题解

  • 12
    @ 7 年前 
    /*
此题很明显是经典的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();
}
    Copy
  • 2
    @ 6 年前

    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;
}
    Copy
  • 1
    @ 4 年前

    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;
}
    Copy
  • 1
    @ 6 年前

    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
    @ 6 年前 
    **将楼上题解翻译成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翻译）
    Copy
  • 1
    @ 7 年前

    //暴力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
    @ 3 年前

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

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

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

  • 0
    @ 4 年前 
    #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; 
}
    Copy

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

  • 0
    @ 5 年前

    三维暴力+滚动优化；

    #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");
}
    Copy
  • 0
    @ 5 年前

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

    #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");
}
    Copy
  • 0
    @ 8 年前

    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;
}
    Copy
    • 其实，你也可以不用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;
}
    Copy
  • 0
    @ 8 年前

    简单背包……
    ```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
    @ 9 年前

    更新记录之前的牌的时候要注意，不然会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
    @ 9 年前

    简单背包，一个数组 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;
    }

    • @ 9 年前

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

  • 0
    @ 9 年前

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

    • @ 8 年前

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

  • 0
    @ 9 年前

    大神们帮我看看怎么优化吧，总是超时，能给我过了的话感激不尽！
    #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
    @ 9 年前

    格式不大好，大家见谅

  • 0
    @ 9 年前

    求大神们帮我看看怎么优化，总是超时。
    #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
    @ 9 年前

    01背包 输出方案有点麻烦

  • 0
    @ 10 年前

    比较暴力的两遍搜索+记忆化....
    这个数据还是比较弱的......
    第一遍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
分类
动态规划 | 背包 点击显示
标签
递交数
6304
已通过
1440
通过率
23%
被复制
13
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1