一道01背包的题目，只不过这一次不是用01背包来求最大值或最小值，而是将背包填满。这只需要将数组dp[]的dp[0]设为0，将其他设为 -∞即可（原因：这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放 入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什 么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于 未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包 都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。）
难点在于记录路径，同时处理多个解的情况。一开始我也想不到要怎么处理多个解的情况(总不能做两次dp吧)，无奈去看题解，恍然大悟。具体见代码中的注释。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF -0x3fffffff
using namespace std;
int w[105];
bool rec[105][100005];
int dp[100005];
int ans[105];
void init()
{
dp[0]=0;
for(int i=1;i<100005;i++) dp[i]=INF;
}
int main()
{
memset(ans,0,sizeof(ans));memset(dp,0,sizeof(dp));dp[0]=1;
memset(rec,0,sizeof(rec));memset(w,0,sizeof(w));
int wei;
cin>>wei;
int n;
cin>>n;
int vtot=0;
for(int i=0;i<n;i++)
cin>>w[i];
for(int i=0;i<n;i++)
for(int j=wei;j>=w[i];j--)
dp[j]+=dp[j-w[i]]; //用动态规划求解解的个数，因为状态是从
//dp[j-w[i]]转移过来的，故每出现一个解
//都会+1，若dp[wei]>1，则说明在wei时有两个解，
//即问题有两个解
if(dp[wei]>1)
cout<<"-1"<<endl;
else if(dp[wei]==0) //如果仍然为0，则说明无解
cout<<"0"<<endl;
else //从这里开始，就是普通的01背包了
{
init();
for(int i=0;i<n;i++)
for(int j=wei;j>=w[i];j--){
int tmp=dp[j-w[i]]+w[i];
dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
if(dp[j]==tmp)
rec[i][j]=1;
}
int sum=0;int cnt=0;
int i=n-1;int j=wei;
while(i>=0&&j>0)
{
if(rec[i][j])
{
ans[i+1]=1;
j-=w[i];
}
i--;
}
int pr=0;
for(int k=1;k<=n;k++)
{
if(!ans[k]){
if(pr)
cout<<" "<<k;
else
cout<<k;
pr=1;
}
}
}
return 0;
}