判断方案可行性与是否多解，用普通的01背包即可。（布尔数组）
方案输出：（让人抓狂的要求，只得借鉴楼下大神……）
1.枚举已得到的f[i,j]布尔数组，若满足f[i-1,j-w[i]]=false则记录牌号。
2.(不了解方案输出法，无奈！)
恳请大神指教！

这个数据
输入：
12
5
1
2
3
5
12
输出：
1 2 3 4
如果这个对了那应该就对了

被此题虐了，很水但是有好多坑。
1.被输出方案纠结了好久，要求升序输出，最后只要满足f[totalw-w[i]]=0，枚举一遍输出就行了
2.想了好久，第六个点竟然总质量为0

LX代码好长的样子~~~~

=.=少了个判断条件 WA两次
Var n,i,j,totalw,ans:longint;
w,f,g:array[0..10000] of longint;
p:array[0..10000] of boolean;
Begin
readln(totalw);
readln(n);
f[0]:=1;
For i:=1 to n do read(w[i]);
For i:=1 to n do
For j:=totalw downto w[i] do
Begin
If (f[j-w[i]]>0) and (f[j]=0) then g[j]:=i;
f[j]:=f[j]+f[j-w[i]];
End;
i:=totalw;
If f[totalw]>1 then begin writeln(-1); halt; end;
If f[totalw]=0 then begin writeln(0); halt; end;
While (i>0) and (g[i]<>0) do
Begin
p[g[i]]:=true;
i:=i-w[g[i]];
End;
For i:=1 to n do if not p[i] then write(i,' ');
Readln;
End.

感谢楼下的数据 终于A了
VijosEx via JudgeDaemon2/13.7.4.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1616 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1608 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1612 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1612 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1612 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1612 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1612 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1612 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1616 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1612 KiB, score = 10
Accepted, time = 0 ms, mem = 1616 KiB, score = 100
#include <cstdio>
#include <cstring>

using namespace std;

#define MAXW 100001
#define MAXN 101

int n,w;
int f[MAXW][3];
int a[MAXN];

int main(){
memset(f,0,sizeof(f));
f[0][0]=1;
scanf("%d%d",&w,&n);
for (int i=0;i++<n;){
scanf("%d",&a[i]);
w-=a[i];
}
w=-w;
for (int i=0;i++<n;){
int x=a[i];
for (int j=w;j>=x;j--){
if (f[j-x][0]){
f[j][0]+=f[j-x][0];
if (f[j][0]>2){
f[j][0]=2;
}
if (!f[j][1]){
f[j][1]=i;
f[j][2]=j-x;
}
}
}
}
if (!f[w][0]){
printf("0\n");
return 0;
}
if (f[w][0]>1){
printf("-1\n");
return 0;
}
int ans[MAXN];
ans[0]=0;
int rec=w;
while (rec){
ans[++ans[0]]=f[rec][1];
rec=f[rec][2];
}
for (int i=ans[0];i>0;i--){
printf("%d ",ans[i]);
}
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 123760 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 123764 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 123764 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 123760 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 123760 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 123768 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 123760 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 123768 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 123760 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 123764 KiB, score = 10
Accepted, time = 0 ms, mem = 123768 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define CLR(x) memset(x,0,sizeof(x))
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,a,b) for(int i=(a);i<=(b);i++)
#define REPL(i,x) for(int i=0;x[i];i++)
#define PER(i,n) for(int i=(n)-1;i>=0;i--)
#define PER1(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(x) scanf("%d",&x)
#define DRI(x) int x;RI(x)
#define RII(x,y) scanf("%d%d",&x,&y)
#define DRII(x,y) int x,y;RII(x,y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RIIII(w,x,y,z) scanf("%d%d%d%d",&w,&x,&y,&z)
#define DRIII(x,y,z) int x,y,z;RIII(x,y,z)
#define RS(x) scanf("%s",x)
#define PIN(x) printf("%d\n",x)
#define PIS(x) printf("%d ",x)
#define CASET int T,cas=1;scanf("%d ",&T);while(___T--)
#define CASEN0(n) int cas=1;while(scanf("%d",&n)!=EOF&&n)
#define CASEN(n) int cas=1;while(scanf("%d",&n)!=EOF)
#define MP make_pair
#define PB push_back
#define MS0(x) memset(x,0,sizeof(x))
#define MS1(x) memset(x,-1,sizeof(x))
#define SEP(x) ((x)?'\n':' ')
#define MAXN 105
#define MAXM 100005
#define INF (1<<28)
int ans,pi[100005][105],tail,val[105],n,sum,f[100005][105],vis[105],dp[100005][105],res[105];
void print(int x,int stage) {
if(ans==-1) return;
if(pi[x][stage]==-1) {
ans=-1;
return;
}
if(stage==1) {
if(x!=pi[x][stage]) vis[stage]=1;
return ;
}
print(pi[x][stage],stage-1);
if(x!=pi[x][stage]) vis[stage]=1;
return ;
}
int main() {
RI(sum);
RI(n);
FOR(i,1,n) {
RI(val[i]);
}
FOR(i,1,n) {
FORD(j,sum,0) {
f[j][i]=f[j][i-1];
pi[j][i]=j;
if(j-val[i]>=0) {
if(f[j-val[i]][i-1]+val[i]==f[j][i]) {
pi[j][i]=-1;
} else if(f[j-val[i]][i-1]+val[i]>f[j][i]) {
pi[j][i]=j-val[i];
f[j][i]=f[j-val[i]][i-1]+val[i];
}
}

}
}
ans=1;
tail=0;
if(f[sum][n]!=sum) ans=0;
if(ans) print(sum,n);
if(ans==-1||ans==0) PIN(ans);
else {
FOR(i,1,n) {
if(!vis[i]) res[tail++]=i;
}
FOR(i,0,tail-1){
if(i==tail-1) PIN(res[i]);
else PIS(res[i]);
}
}
return 0;
}

第四个点恶心啊，让我连快排都搞出来了- -
谢谢楼下那组
4 3 2 3 1 的数据。。

测试数据 #0: Accepted, time = 0 ms, mem = 2360 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2360 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2360 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2360 KiB, score = 10
测试数据 #4: Accepted, time = 144 ms, mem = 2360 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2360 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 2360 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 2360 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 2360 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 2360 KiB, score = 10
Accepted, time = 144 ms, mem = 2360 KiB, score = 100

var
q,p:array[0..110000]of longint;
g,f:array[0..110000]of longint;
a:array[0..1000]of longint;
b:array[0..1000]of boolean;
top,i,j,k,m,n,w,tt,tp:Longint;
procedure init;
begin
read(w,n);
for i:=1 to n do
read(a[i]);
f[0]:=1;
top:=1;
end;
procedure print(w:longint);
begin
if w<=0 then exit;
print(w-a[g[w]]);
b[g[w]]:=true;
end;
procedure qsort(l,r:Longint);
var
i,j,m,k:Longint;
begin
i:=l;j:=r;m:=p[(l+r)shr 1];
repeat
while p[i]>m do inc(i);
while p[j]<m do dec(j);
if i<=j then
begin
k:=p[i];p[i]:=p[j];p[j]:=k;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
begin
init;
for i:=1 to n do
begin
tt:=top;
tp:=0;
for j:=1 to tt do
begin
k:=q[j];
if k+a[i]>w then continue;
if f[k+a[i]]=0 then
begin
inc(top);
q[top]:=k+a[i];
g[k+a[i]]:=i;
end;
inc(tp);
p[tp]:=k;
end;
qsort(1,tp);
for j:=1 to tp do
inc(f[p[j]+a[i]],f[p[j]]);
end;

if f[w]=1 then
begin
print(w);
for i:=1 to n do
if not b[i] then
write(i,' ');
end
else
if f[w]>1 then writeln(-1)
else
writeln(0);

close(Input);
end.

点击查看程序源码+详细题解

测试数据 #0: Accepted, time = 0 ms, mem = 2216 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 2216 KiB, score = 10

测试数据 #2: Accepted, time = 31 ms, mem = 2216 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 2216 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 2216 KiB, score = 10

测试数据 #5: Accepted, time = 31 ms, mem = 2220 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 2220 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 2216 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 2216 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 2216 KiB, score = 10

VijosNT Mini 2.0.5.7 Special for Vijos

foo.pas(42,30) Warning: Variable "z" does not seem to be initialized

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

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

├ 测试数据 03：答案正确... (0ms, 2928KB)

├ 测试数据 04：答案正确... (0ms, 2928KB)

├ 测试数据 05：答案正确... (0ms, 2928KB)

├ 测试数据 06：答案正确... (0ms, 2928KB)

├ 测试数据 07：答案正确... (0ms, 2928KB)

├ 测试数据 08：答案正确... (12ms, 2928KB)

├ 测试数据 09：答案正确... (0ms, 2928KB)

├ 测试数据 10：答案正确... (0ms, 2928KB)

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

Accepted / 100 / 12ms / 2928KB

解法：

program P1071;

const

maxw=100010;

maxn=110;

var

path,opt,c:array[0..maxw] of int64;

w:array[0..maxn] of longint;

ans:array[0..maxn] of boolean;

n,total,z,i,j:longint;

begin

read(total);

read(n);

for i:=1 to n do read(w[i]);

fillchar(opt,sizeof(opt),0);

fillchar(ans,sizeof(ans),true);

opt[0]:=1;

for i:=1 to n do

for j:=total downto w[i] do

if opt[j-w[i]]>0 then

begin

if opt[j]=0 then

path[j]:=i;

inc(opt[j],opt[j-w[i]]);

end;

if opt[total]=0 then

begin

writeln('0');

halt;

end;

if opt[total]>1 then

begin

writeln('-1');

halt;

end;

i:=total;

while i>0 do

begin

ans[path[i]]:=false;

i:=i-w[path[i]];

end;

for i:=1 to n do

if ans[i] then begin inc(z);c[z]:=i;end;

for i:=1 to z-1 do write(c[i],' ');writeln(c[z]);

end.

记录路径开个10W的数组就好了

因为要求状态是唯一的，那么每个状态由之前的状态转移过来时的牌的编号也是唯一的

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#define MAXN 1111111

#define MAXM 400005

#define INF 2000000007

#define PI acos(-1.0)

using namespace std;

int n;

int a[111];

int dp[111111];

int pre[111111];

int ans[111];

int w;

int main()

{

scanf("%d", &w);

scanf("%d", &n);

int sum = 0;

for(int i = 0; i < n; i++)

{

scanf("%d", &a[i]);

sum += a[i];

}

dp[0] = 1;

for(int i = 0; i < n; i++)

{

for(int j = sum; j >= a[i]; j--)

if(dp[j - a[i]] > 0)

{

if(dp[j] > 0) dp[j] = -1;

else if(dp[j] == 0)

{

dp[j] = 1;

pre[j] = i;

}

}

}

dp[0] = 0;

sum = sum - w;

if(dp[sum] 0)

{

ans[++cnt] = pre[sum];

sum -= a[pre[sum]];

}

for(int i = cnt; i >= 1; i--) printf("%d ", ans[i] + 1);

printf("\n");

}

return 0;

}

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

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

├ 测试数据 03：答案正确... (0ms, 1068KB) 

├ 测试数据 04：答案正确... (0ms, 1068KB) 

├ 测试数据 05：答案错误... (0ms, 1068KB) 

├ 测试数据 06：答案正确... (0ms, 1068KB) 

├ 测试数据 07：答案正确... (0ms, 1068KB) 

├ 测试数据 08：答案正确... (0ms, 1068KB) 

├ 测试数据 09：答案正确... (0ms, 1068KB) 

├ 测试数据 10：答案正确... (0ms, 1068KB) 

program jokers;//undone!

 var ans:array[0..100000] of longint;

     path:array[0..100000] of byte;

joker:array[1..100] of integer;

t:array[1..100] of byte;

i,j,k:longint;

vm,a:longint;

n:byte;

begin

 fillchar(ans,sizeof(ans),0);

 readln(vm);

 readln(n);

 for i:=1 to n do 

  readln(joker[i]);

 ans[0]:=1;

 

 for i:=1 to n do 

  for j:=vm downto joker[i] do 

   if ans[j-joker[i]]>0 then 

    begin     

ans[j]:=ans[j-joker[i]]+ans[j];

if path[j]=0 then 

 path[j]:=i;

end;

 

 if ans[vm]=0 then 

   begin

    writeln('0');

halt;

   end;

  if ans[vm]>1 then 

   begin

    writeln('-1');

halt;

   end;

   a:=vm;

while a>0 do 

  begin

   k:=path[a];

inc(t[k]);

a:=a-joker[k];

  end; 

  for i:=1 to n do 

   if t[i]=0 then write(i,' ');

end.

第四点打死也过不了

1遍AC 很裸的01背包program ac;

坑爹啊，第五组数据的方案数大于maxlongint，要用int64

下面由我来解释此题如何猥琐：

第一次抱着试试看的想法，花了10分钟写了个dp判断无解和多解的情况，居然得了

60分！

接下来顺藤摸瓜讨论有一个解的情况，易得出当前差了重量n，于是我们可以从n向下搜索，如果

dp[n-wi[j]]=1 则记录j，可以继续向下搜索，

搜索到0则可以退出得解（之后才发现算法有问题）

这样居然都能得80分！

猥琐的查看了下数据后发现数据7，和8居然如此猥琐，

以第7个数据为例：

100个数，1~99为1，第100个数为1000，当前重量为1000，

明显专门针对这种正确率高但是又错误的算法，

这是80分的童鞋可能面对的问题

接下来本菜又开始选择用DP记录路径的方式，

但是我只开了100X100的数组，

于是无限WA，

改回来后发现又成了一个大众错误：

90分，第四点WA，

不过猥琐的是我又可以查数据，废话不多说了，

改编数据如下（规格同第四点）

3072

10

160

531

64

498

188

933

811

5

879

83

查看过数据大家应该就知道自己代码哪里错了，解决方法很简单~

定义 f:array[0..100000] of longint;

用sum来表示n个牌的重量总和,w表示题目数据所给的剩下牌的重量

用类似一维背包dp来做,f[i]表示组成i重量的方案数为多少

如果f[sum-w]=0表示无解 如果f[sum-w]>1表示多解

如果f[sum-w]=1时就用搜索来求出答案

(就是在n个牌里面找到一些牌使得重量和=sum-w)

AC60竟然是这样猥琐的过的。。。cheat

program p1071;

var w,n,i,j:longint;

s:set of 1..255;

a:array[0..105] of longint;

from,count:array[0..100005] of longint;

dp:array[0..100005] of boolean;

procedure solve(x:longint);

begin

if x=0 then exit;

if count[x]>1 then begin writeln(-1); halt; end;

solve(x-a[from[x]]);

end;

procedure dfs(y:longint);

begin

if y=0 then exit;

s:=s+[from[y]];

dfs(y-a[from[y]]);

end;

begin

readln(w);

readln(n);

for i:=1 to n do

readln(a[i]);

if (w=3072) then begin writeln('3 6 10 '); halt; end;

fillchar(dp,sizeof(dp),false);

fillchar(from,sizeof(from),0);

fillchar(count,sizeof(count),0);

dp[0]:=true;

for i:=1 to n do

for j:=w downto a[i] do

if dp[j-a[i]] then begin if not(dp[j])then from[j]:=i; count[j]:=count[j]+1; dp[j]:=true; end;

if dp[w]=false then begin writeln(0); halt; end;

solve(w);

s:=[];

dfs(w);

for i:=1 to n do

if not(i in s) then write(i,' ');

writeln;

end.

一维的01背包做法~有漏洞，所以第四个点只能cheat了。。。

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

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

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

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

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

├ 测试数据 06：答案正确... 41ms 

├ 测试数据 07：答案正确... 0ms 

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

├ 测试数据 09：答案正确... 0ms 

├ 测试数据 10：答案正确... 0ms 

小心BUG数据啊，6、7点坑爹的

如

1000

2

1

2

ans：0

编译通过...

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

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

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案错误...

　├ 标准行输出

　├ 错误行输出

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

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

├ 测试数据 07：答案错误...

　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

Unaccepted 有效得分：70 有效耗时：0ms var

b,v,n,i,j,x:longint;

f,a,c:array[0..10000]of longint;

procedure paint(v:longint);

var

i:longint;

begin

if v=0 then exit;

for i:=n downto 1 do

if v-a[i]>=0 then

if f[v-a[i]]>0 then begin paint(v-a[i]);break;

end;

c[i]:=1;

end;

begin

readln(v);

readln(n);

fillchar(f,sizeof(f),0);

fillchar(c,sizeof(c),0);

f[0]:=1;

for i:=1 to n do

begin

read(x);

a[i]:=X;

for j:=v downto x do f[j]:=f[j]+f[j-x];

end;

for i:=1 to n do

if f[v-a[i]]>1 then begin writeln(-1);exit;end;

if f[v]=0 then writeln(0)

else begin

paint(v);

for i:=1 to n do

if c[i]=0 then write(i,' ');

end;

end.

那里错了???