Feown


私信TA

用户名:uq_13516770928

访问量:4276

签 名:

等  级
排  名 3473
经  验 1817
参赛次数 0
文章发表 21
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

一看是背包就想用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;
}


 

0.0分

1 人评分

  评论区