当前位置:网站首页>与利润无关的背包问题(深度优先搜索)
与利润无关的背包问题(深度优先搜索)
2022-07-06 23:08:00 【疯疯癫癫才自由】
/**< 1th example) */
/** \brief
* 在九件物品中选出3件使其重量和500克之差的绝对值最小
* \求出物体编号
* \param
* \return
*
*/
/**< 循环求解,循环求解只能处理选择特定的物品数量,不具有普遍性; */
/**< 1th example) */
/** \brief
* 在九件物品中选出3件使其重量和500克之差的绝对值最小
* \求出物体编号
* \param
* \return
*
*/
/**< 循环求解 */
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n=9,abs_cha=1000;
int matr[n+1];
cout << "输入" << n << "件物品的重量:\n";
for(int i=1;i<=n;++i)
cin >> matr[i];
int besti,bestj,bestk;
int bestw,temp_sum=0;
for(int i=1;i<=7;++i)
for(int j=i;j<=8;++j)
for(int k=j;k<=9;++k)
{
temp_sum=matr[i]+matr[j]+matr[k];
if(abs(temp_sum-500)<abs_cha)
{
bestw=temp_sum;
abs_cha=abs(temp_sum-500);
besti=i;
bestj=j;
bestk=k;
}
}
printf("choose index is : %d %d %d \n",besti,bestj,bestk);
printf("best weight is:%d",bestw);
return 0;
}
/** \brief
* 在n件物品中选出k件使其重量和500克之差的绝对值最小
* \求出物体编号
* \param
* \return
*
*/
/**< 深度优先搜索求解 */
/** \brief
* 在n件物品中选出k件使其重量和500克之差的绝对值最小
* \求出物体编号
* \param
* \return
*
*/
/**< 深度优先搜索求解 */
/**
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> ans,temp;
int bestw=0,abs_cha=1000;
int matr[10];
void DFS(int index,int sum,int weight);
int main()
{
int n,sum;
cout << "输入物品的总数量以及要选择的物品数量:\n";
cin >> n >> sum;
cout << "输入" << n << "件物品的重量:\n";
for(int i=1;i<=n;++i)
cin >> matr[i];
DFS(1,0,0);
printf("choose index is : \n");
for(size_t i=0;i<ans.size();++i)
cout << ans[i] << ' ';
cout << endl;
printf("best weight is:%d",bestw);
return 0;
}
void DFS(int index,int sum,int weight)
{
if(index>9||sum>3||abs_cha<weight-500)//< 这里不能加绝对值
return;
if(sum==3)
{
if(abs_cha>abs(weight-500))
{
ans=temp;
bestw=weight;
abs_cha=abs(weight-500);
}
return;
}
temp.push_back(index);
if(weight+matr[index]-500<abs_cha) //这样能稍微节约一点时间,不至于每个物品都去选择
DFS(index+1,sum+1,weight+matr[index]); //因为abs_cha一定是一个非负数,当weight+matr[index]-500
temp.pop_back(); //比abs_cha还大时,那么这个组合一定不是最佳选择的组合
DFS(index+1,sum,weight);
}
*/
/**< 2th example */
/** \brief
* 有一个背包可以放入的物品重量为S,现有n件物品,
* \ 问能否从这n件物品中选择若干件放入背包,使得放入的
* \ 重量之和恰为S
* \return
*
*/
/** \brief 递归设计分析
* Knap(s,n)表示背包的容量还剩余s,还有n件物品没进行选择
* \
* \param
* \return
*
*/
这个递归函数蛮不错的,直接在递归函数里输出下标,可以学习学习。这是在算法设计与分析教材上看的。
/**< 2th example */
/** \brief
* 有一个背包可以放入的物品重量为S,现有n件物品,
* \ 问能否从这n件物品中选择若干件放入背包,使得放入的
* \ 重量之和恰为S
* \return
*
*/
/** \brief 递归设计分析
* Knap(s,n)表示背包的容量还剩余s,还有n件物品没进行选择
* \
* \param
* \return
*
*/
#include <iostream>
using namespace std;
const int maxn=10;
int matr[maxn];
bool Knap(double rest,int unselected );
int main()
{
int n;
double s;
cout << "输入物品数量及背包容量:\n";
cin >> n >> s;
cout << "输入" << n<< "件物品的重量:\n";
for(int i=1;i<=n;++i)
cin >> matr[i];
if(Knap(s,n)==false)
cout << "No solution\n";
return 0;
}
bool Knap(double rest,int unselected )
{
if(rest==0)
return true;
else if(rest<0||(rest>0&&unselected<1))
return false;
else if(Knap(rest-matr[unselected],unselected-1)==true) //选择第unselected件物品
{
cout << "choose : " << unselected << "th" << endl;
return true;
}
else
return Knap(rest,unselected-1);//不选择第unselected件物品
}
/**< 2th example */
/** \brief
* 有一个背包可以放入的物品重量为S,现有n件物品,
* \ 问能否从这n件物品中选择若干件放入背包,使得放入的
* \ 重量之和恰为S
* \return
*
*/
/** \brief 深度优先搜索分析
* Knap(index,sum_value)表示此时对第index件物品进行选择,已选择的物品
* \ 重量为sum_value
* \param
* \return
*
*/
/**< 2th example */
/** \brief
* 有一个背包可以放入的物品重量为S,现有n件物品,
* \ 问能否从这n件物品中选择若干件放入背包,使得放入的
* \ 重量之和恰为S
* \return
*
*/
/** \brief 深度优先搜索分析
* Knap(index,sum_value)表示此时对第index件物品进行选择,已选择的物品
* \ 重量为sum_value
* \param
* \return
*
*/
#include <iostream>
#include <vector>
using namespace std;
const int maxn=10;
int matr[maxn];
int n;
double s;
vector<int> ans,temp;
void Knap(int index,double sum_value);
void output();
int pos=1;
int main()
{
cout << "输入物品数量及背包容量:\n";
cin >> n >> s;
cout << "输入" << n<< "件物品的重量:\n";
for(int i=1;i<=n;++i)
cin >> matr[i];
Knap(1,0);
return 0;
}
void Knap(int index,double sum_value)
{
if(index>n||sum_value>s)
return;
if(sum_value==s)
{
ans=temp;
output();
return ;
}
temp.push_back(index);
if(sum_value+matr[index]<=s)
Knap(index+1,sum_value+matr[index]);
temp.pop_back();
Knap(index+1,sum_value);
}
void output()
{
cout << pos++ << "th:\n";
for(size_t i=0;i<ans.size();++i)
{
cout << "choose " << ans[i] << "th\n";
}
}
边栏推荐
- Function pointer and pointer function in C language
- 【最佳网页宽度及其实现】「建议收藏」
- STM32 encapsulates the one key configuration function of esp8266: realize the switching between AP mode and sta mode, and the creation of server and client
- STM32F103实现IAP在线升级应用程序
- 当 Knative 遇见 WebAssembly
- JS variable plus
- [736. LISP syntax parsing]
- vector和类拷贝构造函数
- Flask项目使用flask-socketio异常:TypeError: function() argument 1 must be code, not str
- A line of R code draws the population pyramid
猜你喜欢
Function pointer and pointer function in C language
Section 1: (3) logic chip process substrate selection
《二》标签
No experts! Growth secrets for junior and intermediate programmers and "quasi programmers" who are still practicing in Universities
Flex layout and usage
C语言中函数指针与指针函数
offer如何选择该考虑哪些因素
AttributeError: module ‘torch._ C‘ has no attribute ‘_ cuda_ setDevice‘
Operand of null-aware operation ‘!‘ has type ‘SchedulerBinding‘ which excludes null.
Ansible中的inventory主机清单(预祝你我有数不尽的鲜花和浪漫)
随机推荐
The sooner you understand the four rules of life, the more blessed you will be
Mysql database (basic)
最全常用高数公式
Field data acquisition and edge calculation scheme of CNC machine tools
Salesforce 容器化 ISV 场景下的软件供应链安全落地实践
Common Oracle SQL statements
Markdown编辑器
《四》表单
JS variable case
Servicemesh mainly solves three pain points
R descriptive statistics and hypothesis testing
Flex layout and usage
DBSync新增对MongoDB、ES的支持
Basic knowledge of road loss of 3GPP channel model
【PHP SPL笔记】
ASP. Net MVC - resource cannot be found error - asp Net MVC – Resource Cannot be found error
[ArcGIS tutorial] thematic map production - population density distribution map - population density analysis
Vscode automatically adds a semicolon and jumps to the next line
Time complexity & space complexity
Leetcode longest public prefix