200 条题解
-
12
PowderHan LV 10 @ 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
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
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
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
**将楼上题解翻译成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
//暴力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
士郎のsaber (hhh_saber) LV 6 @ 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
#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
caimengzhe LV 4 @ 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
其实这道题可以三维暴力+滚动优化；
#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
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
简单背包……
```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
更新记录之前的牌的时候要注意，不然会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
wang_yanheng LV 10 @ 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;
}-
winterfell30 @ 2016-04-09 15:32:38
Print函数里面的循环不应该是begin+1到n么？
-
-
0
2868647513 LV 8 @ 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
格式不大好，大家见谅
-
0
求大神们帮我看看怎么优化，总是超时。
#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
比较暴力的两遍搜索+记忆化....
这个数据还是比较弱的......
第一遍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;
}
PowderHan
LV 10
@ 2017-05-07 22:28:16
信息
- ID
- 1071
- 难度
- 7
- 分类
- 动态规划 | 背包 点击显示
- 标签
- 递交数
- 6302
- 已通过
- 1439
- 通过率
- 23%
- 被复制
- 13
- 上传者
-
xiaomengxian
