1 /* 2 这道题目有一定的思维量， 3 说是有M,L两个总量，A[1]...A[N]， 4 最后要使得 M+L>=sum（A[1]...A[N]）....其中A[i]必须用其中一种装 5 之前的想法： 6 用 dp[i][j]：表示装到第i个物品，M中还有j没装，我们知道(M-j)+(L-j‘)=sum[i] 7 就能得出j‘，现在我们发现，尽可能得用M去装，找到M最多能装的物品的总量，剩下的用 8 L去装，只要L大于这个还没装的量就行了。 9 这样就是一个01背包的问题。10 转换模型很重要11 */12 13 #include <iostream>14 #include <string.h>15 #include <stdio.h>16 17 using namespace std;18 bool dp[2010];//背包用了i的状态19 int A[2010],path[2010],ans[2002];20 int M,L,N,sum;21 int main()22 {23     while(~scanf("%d%d",&M,&L)){24         if (M==0 && L==0) break;25         sum=0;26         scanf("%d",&N);27         for(int i=1;i<=N;i++) scanf("%d",&A[i]),sum+=A[i];28 29         memset(dp,0,sizeof(dp));30         dp[0]=true;31         memset(path,0,sizeof(path));//path=1表示选择了M32         if (L+M<sum) {33             printf("Impossible to distribute\n");34             continue;35         }36         for (int i=1;i<=N;i++){37             for(int V=M;V-A[i]>=0;V--){38                 if (dp[V-A[i]]) {39                     dp[V]=true;40                     if (!path[V]) path[V]=i;//这句是关键，41                 }42             }43         }44         int v;45         for(v=M;v>=0;v--){46             if (dp[v]) break;47         }48         if ((v==-1 && sum>L) || (dp[v] && sum-v>L)){49             printf("Impossible to distribute\n");50             continue;51         }52         int ansn=0;53         while(v>0){54             ans[ansn++]=path[v];55            // cout<<path[A[v]]<<" ";56             v-=A[path[v]];57            // cout<<"v="<<v<<endl;58         }59         printf("%d",ansn);60         for(int i=ansn-1;i>=0;i--) printf(" %d",ans[i]);61         printf("\n");62     }63     return 0;64 }