01背包详解

01背包

一、问题引出

现在一共有 N N N 件物品，第i（i从1开始）件物品的重量为 v [ i ] v[i] v[i] ，价值为 w [ i ] w[i] w[i] 。每个物品至多挑选一次，且在挑选出来的物品的总重量不超过 V V V 的情况下，能装入背包的物品的总价值和最大为多少

二、分析 2.1 暴力思考

对于每一个物品我们无非就两种选择， 选 和 不选 那么对于N件物品的抉择方案数就是 2 N 2^N 2N 种，当 N < 27 N < 27 N V || vis[loc]) return; if(loc == n + 1){ ans = max(ans,res_w); return; } vis[loc] = 1; dfs(loc+1,sum_v + v[loc],res_w + w[loc]);//选取第loc个位置的数 vis[loc] = 0; dfs(loc+1,sum_v,res_w);//不选去第loc个位置的数 } int main() { scanf("%d%d",&n,&V); memset(vis,false,sizeof vis); ans = 0; for(int i = 1;i