描述

過年的時候，大人們最喜歡的活動，就是打牌了。xiaomengxian不會打牌，只好坐在一邊看著。
這天，正當一群人打牌打得起勁的時候，突然有人喊道：“這副牌少了幾張！”眾人一數，果然是少了。于是這副牌的主人得意地說：“這是一幅特制的牌，我知道整副牌每一張的重量。只要我們稱一下剩下的牌的總重量，就能知道少了哪些牌了。”大家都覺得這個辦法不錯，于是稱出剩下的牌的總重量，開始計算少了哪些牌。由于數據量比較大，過了不久，大家都算得頭暈了。
這時，xiaomengxian大聲說：“你們看我的吧！”于是他拿出筆記本電腦，編出了一個程序，很快就把缺少的牌找了出來。
如果是你遇到了這樣的情況呢？你能辦到同樣的事情嗎？
格式

輸入格式

第一行一個整數TotalW，表示剩下的牌的總重量。
第二行一個整數N（<=100），表示這副牌有多少張。
接下來N行，每行一個整數Wi（1<=Wi<=1000），表示每一張牌的重量。
輸出格式

如果無解，則輸出“0”；如果有多解，則輸出“-1”；否則，按照升序輸出丟失的牌的編號，相鄰兩個數之間用一個空格隔開。
樣例1

樣例輸入1

270
4
100
110
170
200
樣例輸出1

2 4
限制

各個測試點1s
提示

Sample input #2
270
4
100
110
160
170
Sample output #2
-1
Sample input #3
270
4
100
120
160
180
Sample output #3
0
來源

Xiaomengxian

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int MAXN=1e2+10,MAXM=1e5+10; int road[MAXM],f[MAXM],wi[MAXM],tot,n; bool inc[MAXM]; int main(){scanf("%d%d",&tot,&n);fo(i,1,n) scanf("%d",&wi[i]);memset(f,0,sizeof(f));memset(road,0,sizeof(road));memset(inc,0,sizeof(inc));f[0]=1;fo(i,1,n){fod(val,tot,wi[i]){if(f[val-wi[i]]){f[val]+=f[val-wi[i]];if(!road[val]) road[val]=i;}}}if(f[tot]>1) printf("-1\n");else if(f[tot]==0) printf("0\n");else{ int val=tot;while(val){inc[road[val]]=1;val-=wi[road[val]];}fo(i,1,n)if(!inc[i]) printf("%d ",i);}return 0; }

總結

以上是生活随笔為你收集整理的vijos 1071 01背包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。