少物品背包DFS也很快_2038: 简化型背包

一看是背包就想用dp动态规划来做，但是因为他是重量跟空间都要考虑我只能开二维数组，而且题目写着空间跟重量<=10000，开个二维的直接200多M的内存过不了；

但是仔细一看他只有5个物品要放入背包，那用DFS也很快；

pp总价值； vv总空间； ww总重量；x当前放第x个物品

参考代码:

#include<iostream>
using namespace std;
int v, w;
int pi[5], vi[5], wi[5];
int ma;
int vis[5];
void dfs(int pp, int vv, int ww, int x){
	if(vv > v || ww > w || x == 5){
		if(pp > ma) {
			ma = pp;
		}
		return;
	}
	dfs(pp, vv, ww, x + 1);//不放当先物品
	if(!vis[x] && (v - vv) >= vi[x] && (w - ww) >= wi[x]){
		vis[x] = 1;
		dfs(pp + pi[x], vv + vi[x], ww + wi[x], x + 1);//放当前物品
		vis[x] = 0;
	}
}
int main(){
	cin>>v>>w;
	for(int i = 0; i < 5; i++){
		cin>>pi[i]>>vi[i]>>wi[i];
	}
	dfs(0, 0, 0, 0);
	cout<<ma;
	return 0;
}