#include<iostream> #include<cstdio> #include<string> #include<cstring> #define LL long long using namespace std; int we,n,a[1050],i,j,dp[110005],num[101000],ans[1050]={0};//变量常量说明 void init() { cin>>we>>n; for(i=1;i<=n;i++) cin>>a[i]; memset(dp,0,sizeof(dp)); dp[0]=1; } void solve() { for(j=1;j<=n;j++) for(i=we;i>=a[j];i--) if(dp[i-a[j]]) { dp[i]+=dp[i-a[j]];//容积i时方案数 if(num[i]==0) num[i]=j;//记录途径 } if(dp[we]==0) cout<<"0"<<endl; if(dp[we]>1) cout<<"-1"<<endl; if(dp[we]==1) { int v=we; while(v) { ans[num[v]]=1;//标记 v-=a[num[v]]; } for(i=1;i<=n;i++) if(ans[i]==0) cout<<i<<' '; } } int main() { freopen("bagb.in","r",stdin); freopen("bagb.out","w",stdout); init(); solve(); return 0; }
过年的时候，大人们最喜欢的活动，就是打牌了。xiaomengxian不会打牌，只好坐在一边看着。
这天，正当一群人打牌打得起劲的时候，突然有人喊道：“这副牌少了几张！”众人一数，果然是少了。于是这副牌的主人得意地说：“这是一幅特制的牌，我知道整副牌每一张的重量。只要我们称一下剩下的牌的总重量，就能知道少了哪些牌了。”大家都觉得这个办法不错，于是称出剩下的牌的总重量，开始计算少了哪些牌。由于数据量比较大，过了不久，大家都算得头晕了。
这时，xiaomengxian大声说：“你们看我的吧！”于是他拿出笔记本电脑，编出了一个程序，很快就把缺少的牌找了出来。
如果是你遇到了这样的情况呢？你能办到同样的事情吗？
【输入格式】
第一行一个整数TotalW，表示剩下的牌的总重量。
第二行一个整数N（1<=N<=100)<n<=100），表示这副牌有多少张。< span="">
接下来N行，每行一个整数Wi（1<=Wi<=1000），表示每一张牌的重量。 </n<=100），表示这副牌有多少张。<>
【输出格式】
如果无解，则输出“0”；如果有多解，则输出“-1”；否则，按照升序输出丢失的牌的编号，相邻两个数之间用一个空格隔开。
【样例输入】
270
4
100
110
170
200
【样例输出】
2 4
********************************************************************************************
该题就是背包问题的变形，本题可设一个数组dp[v],表示当背包的容量为v时的方案数，记dp[0]=1;再用一个数组path[i]表示容积为i时所放的背包编号，最后用一个while循环标记当v==n时所放的背包编号，如果dp[n]==1时，输出没被标记的背标包编号；如果dp[n]==0,输出相应的值，如果dp[n]>1时，输出相应的值。
*********************************************************************************************************************