后台-插件-广告管理-内容页广告位一(手机)

您现在的位置是:首页 > 开发类 > 游戏开发游戏开发

0-1背包问题(回溯法)

2021-06-05 09:11:11游戏开发人已围观

简介0-1背包问题题目答案注意题目使用回溯法求解0-1背包问题。 给定n(n<=10)种物品和一个容量为c的背包。物品i的重量是wi,价值为vi,背包的容量为C(C<=100)。 在装入背包的物品时,对每种物品只有两个选择:装入或不装入。 如何选择装入背包中的物品,使得装入背包中物品的总价值最大?输入格式:第1行,输入物品个数n和背包容量c 第2行-n+1行,每个物品的重量和价值输出格式:第1行:背包能获得的最大价值 第2行:装入背包的物品编号序列(物品编号从1开始,每个编号后面跟

0-1背包问题

  • 题目
  • 答案
  • 注意

题目

使用回溯法求解0-1背包问题。 给定n(n<=10)种物品和一个容量为c的背包。物品i的重量是wi,价值为vi,背包的容量为C(C<=100)。 在装入背包的物品时,对每种物品只有两个选择:装入或不装入。 如何选择装入背包中的物品,使得装入背包中物品的总价值最大?

输入格式:
第1行,输入物品个数n和背包容量c 第2行-n+1行,每个物品的重量和价值

输出格式:
第1行:背包能获得的最大价值 第2行:装入背包的物品编号序列(物品编号从1开始,每个编号后面跟1个空格;如果没有一个物品可以装入背包,输出nothing)

输入样例:
在这里给出一组输入。例如:

5 10
2 6
2 3
6 5
5 4
4 6

输出样例:
在这里给出相应的输出。例如:

15
1 2 5 

答案

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int wei,val;//重量,价值 
}node[10];
int n,vol,Max=0;//背包数,容量 
int vis[10],tmp[10],ans[10];

void dfs(int level,int choice)
{
	vis[level]=1;
	tmp[level]=choice;
	int t=0;
	for(int i=0;i<=level;i++)
	{
		t+=tmp[i]*node[i].wei;
	//		cout<<tmp[i]<<" ";
	}
	//	cout<<endl<<t<<endl;
	if(t>vol) return;
	if(level==n-1)
	{
		int sum=0;
		for(int i=0;i<n;i++)
		{
			sum+=tmp[i]*node[i].val;
//			cout<<tmp[i]<<" ";
		}
//		cout<<endl;
		if(sum>=Max)
		{
			Max=sum;
			for(int i=0;i<n;i++)
			ans[i]=tmp[i];
		}
	}
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
		{
			dfs(i,1);
			dfs(i,0);
			vis[i]=0;
		}
	}
}

int main()
{
	cin>>n>>vol;
	for(int i=0;i<n;i++)
	cin>>node[i].wei>>node[i].val;
	for(int i=0;i<n;i++)
	{
		fill(vis,vis+n,0);
		fill(tmp,tmp+n,0);
		dfs(i,0);
		dfs(i,1);
	}
	cout<<Max<<endl;
	int flag=1;
	for(int i=0;i<n;i++)
	{
		if(ans[i])
		{
			cout<<i+1<<" ";
			flag=0;
		}
	}
	if(flag) cout<<"nothing";
}

注意

这道题需要对当前节点0和1的情况各自遍历一遍,即

if(!vis[i])
{
	dfs(i,1);
	dfs(i,0);
	vis[i]=0;
}

文章来源:https://blog.csdn.net/ljhsq/article/details/117526456

Tags:PTA 

很赞哦! ()

后台-插件-广告管理-内容页广告位二(手机)

相关文章

后台-插件-广告管理-内容页广告位三(手机)
后台-插件-广告管理-内容页广告位四(手机)

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计60036篇文章
  • 浏览统计4401次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们