本文主要是介绍网易在线笔试牛牛的背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
背包问题首先想到的就是动态规划了，但是这相当于遍历没一种可能性，当背包容量足够大，
零食种类足够多的时候就会出现超时的情况。
问题等价于 
其中， 
表示第i个放入还是不放入， 设state(i,w)表示i个零食放入背包小于等于W的个数，把state(i,w)分解，可以分解为两个情况：
1、是第 i个不放入时，前i-1个零食放入背包小于等于W的种数即state(i-1,w)；
2、是在第i个放入的情况下，前i-1个零食放入背包体积小于等于W-v[i]的个数即state(i-1,w-v[i]);
即 state(i,w) = state(i-1,w) + state(i-1,w-v[i])
边界条件：i = 1时，state(1,w1) 此时如果w1 >0 且v[1]<=w1,state(1,w1) = 2,即有可放入和不放入两种；
i = 1 时，swate(1,w1)此时如果w1 >0且v[1] > w1,state(1,w1)=1,即只有不放入一种；
如果state(i,w)中出现w<=0,则state(i,w)=0;
例子：零食体积1 2 4，w=10
则 state(3,10) = state(2,10) + state(2,6)
= state(1,10) + state(1,8) + state(1,6) + state(1,4)
= 2 + 2 + 2 + 2 = 8
采用递归解法：AC率80%。简简单单的代码实现如下
#include<iostream>
#include<vector>
using namespace std;int f(int n1, int n2,vector<int> &num)
{if(n2 <= 0){return 0;}if(n1 == 1){if(num[n1] <= n2){return 2;}else{return 1;}}return f(n1-1,n2,num) + f(n1 - 1,n2-num[n1],num);
}
int main()
{int n1,sum;cin >> n1 >> sum;vector<int> res(n1 + 1);for(int i=1;i<=n1;i++){cin >> res[i];}cout << f(n1,sum,res) << endl; return 0;
}#include <iostream>
#include <vector>
#include <cmath> //pow()函数头文件
using namespace std;
long long n, w;
vector<long long> good;
long long result = 0;void dfs(int cur, long long sum)
{
if (sum <= w && cur == n)
result++;
if (cur == n || sum > w)
return;
dfs(cur + 1, sum + good[cur]);
dfs(cur + 1, sum); //两次递归，相当于实现了选与不选，第二次是回溯的关键
}int main() {
cin >> n >> w;
good.resize(n);
long long sum = 0;
for (int i = 0; i < n; i++) {
cin >> good[i];
sum += good[i];
}
if (sum <= w) {
//全部都可以放入
result = pow(2, n);
}
else { //注意这里没加排序，加上会更好
dfs(0, 0);
}
cout << result << endl;
return 0;
}
//这个方法是别人的 DFS中看不到回溯，反正我是没看懂
#include<iostream>
#include<algorithm>
using namespace std;
long long nums = 1;
void DFS(vector<long long>& array, int size , long long w, long long sum, int pos){if(sum <= w){nums++;for(int i = pos + 1 ; i < size ; ++i) //问题就出现在这里{DFS(array,size,w,sum+array[i],i);}}
}
int main()
{int n;long long w;cin >>n >> w;long long total = 0;vector<long long > array(n,0);for(int i = 0 ; i != n ; ++i){cin >> array[i];total += array[i];}if(total <= w){nums = pow(2,n);}else{sort(array.begin(),array.end()); //对数组进行排列，难道问题出现在这里？？？？？？ for(int i = 0 ; i != n ; ++i) //问题也出现在这里，这两个for循环DFS(array, array.size(), w, array[i],i);}cout<<nums<<endl;return 0;
}#include <stdio.h>
#include <stack>
using namespace std;
struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode (int x):val(x),left(NULL),right(NULL){}
};
// 非递归的后续遍历，另需要一个辅助指针
void preorder2(TreeNode *node)
{stack<TreeNode *> stack;TreeNode * p =node; //p是个工作指针TreeNode * pree ; //p是个前驱指针，记录访问过的节点int flag =1; while(p || !stack.empty()){while(p!=NULL) { //左子树一直入栈 stack.push(p); //printf("[%d]\n",p->val); p = p ->left; } pree = NULL; flag =1; //辅助变量为1表示当前节点的左孩子为空或者已经被访问过 while(!stack.empty() && flag==1) { p =stack.top(); //如果右结点为空，或者左结点之前遍历过，打印根结点 if( p->right ==pree ) { printf("[%d]\n",p->val); pree = p; stack.pop(); } else //处理右孩子 {p = p -> right; flag = 0; //*p的左孩子未被访问 } } } }
int main()
{ TreeNode a(1); TreeNode b(2); TreeNode c(5); TreeNode d(3); TreeNode e(4); TreeNode f(6); a.left =&b; a.right =&c; b.left =&d; b.right =&e; c.right = &f; //preorder(&a,0); preorder2(&a); return 0;}这篇关于网易在线笔试牛牛的背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
