本来想的算法是如果V<=100000就直接进行01背包时间复杂度为O(30*100000),如果大于100000大于部分贪心选择，剩余部分在进行01背包，可是中间会出现很多问题，大于部分的的处理不好弄，如果100000加上处理后的剩余部分会出现数组越界，再说有的数据也不会过，这只是一种yy的方法，不对。
后来据说是爆搜解决01背包想了想时间复杂度能够达到（10^9自己不敢写，竟没有想到剪枝弄好了能够过，于是就写了起来，这里首先从大到小排序，这样大的在前边保证先装大的，背包容量就会变小再加剪枝就能过了。
View Code #include#include #define maxn 44using namespace std;int w[maxn],n,b[maxn];int V,ans;int cmp(int a,int b){ return a > b;}void dfs(int sum,int num){ if (sum > V) return ; if (num >= n) { ans = max(ans,sum); return ; } int tmp = sum; if (num > 0) tmp += (b[n - 1] - b[num - 1]);//如果当前加上剩余没有选的物品的总和小于原来最大的 if (tmp < ans) return ; dfs(sum + w[num],num + 1); dfs(sum,num + 1);}int main(){ int i,ni; while (~scanf("%d%d",&ni,&V)) { for (int i = 0; i < ni; ++i) scanf("%d",&w[i]); int s = 0; n = 0; for (int i = 0; i < ni; ++i) { b[i] = 0; if (w[i] <= V)//将大于总容量的物品剪掉 { w[n++] = w[i]; s += w[i]; } } if (s <= V)//总和小于总容量 { printf("%d\n",s); continue; } sort(w,w + n,cmp); //b记录前i项和 b[0] = w[0]; for (i = 1; i < n; ++i) b[i] = b[i - 1] + w[i]; ans = 0; dfs(0,0); printf("%d\n",ans); } return 0;}