当前位置:网站首页>Knapsack problem unrelated to profit (depth first search)
Knapsack problem unrelated to profit (depth first search)
2022-07-07 05:09:00 【Madness makes freedom】
/**< 1th example) */
/** \brief
* Choose from nine items 3 Make its weight equal to 500 The absolute value of the difference between grams is the smallest
* \ Find the object number
* \param
* \return
*
*/
/**< Loop solution , Loop solving can only deal with selecting a specific number of items , Not universal ; */
/**< 1th example) */
/** \brief
* Choose from nine items 3 Make its weight equal to 500 The absolute value of the difference between grams is the smallest
* \ Find the object number
* \param
* \return
*
*/
/**< Loop solution */
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n=9,abs_cha=1000;
int matr[n+1];
cout << " Input " << n << " The weight of an item :\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
* stay n Choose from items k Make its weight equal to 500 The absolute value of the difference between grams is the smallest
* \ Find the object number
* \param
* \return
*
*/
/**< Depth first search solution */
/** \brief
* stay n Choose from items k Make its weight equal to 500 The absolute value of the difference between grams is the smallest
* \ Find the object number
* \param
* \return
*
*/
/**< Depth first search solution */
/**
#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 << " Enter the total number of items and the number of items to select :\n";
cin >> n >> sum;
cout << " Input " << n << " The weight of an item :\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)//< Absolute value cannot be added here
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) // This will save a little time , Not every item should be chosen
DFS(index+1,sum+1,weight+matr[index]); // because abs_cha It must be a non negative number , When weight+matr[index]-500
temp.pop_back(); // Than abs_cha When I was young , Then this combination must not be the best choice
DFS(index+1,sum,weight);
}
*/
/**< 2th example */
/** \brief
* There is a backpack that can hold items weighing S, existing n Item ,
* \ Ask if it's possible to n Select several items from the items and put them into the backpack , Make it put in
* \ The sum of the weights is just S
* \return
*
*/
/** \brief Recursive design analysis
* Knap(s,n) Indicates that the capacity of the backpack is still left s, also n Items are not selected
* \
* \param
* \return
*
*/
This recursive function is quite good , Output subscripts directly in recursive functions , You can learn . This is seen in the textbook of algorithm design and analysis .
/**< 2th example */
/** \brief
* There is a backpack that can hold items weighing S, existing n Item ,
* \ Ask if it's possible to n Select several items from the items and put them into the backpack , Make it put in
* \ The sum of the weights is just S
* \return
*
*/
/** \brief Recursive design analysis
* Knap(s,n) Indicates that the capacity of the backpack is still left s, also n Items are not selected
* \
* \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 << " Enter the number of items and backpack capacity :\n";
cin >> n >> s;
cout << " Input " << n<< " The weight of an item :\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) // Select the first unselected Item
{
cout << "choose : " << unselected << "th" << endl;
return true;
}
else
return Knap(rest,unselected-1);// No choice unselected Item
}
/**< 2th example */
/** \brief
* There is a backpack that can hold items weighing S, existing n Item ,
* \ Ask if it's possible to n Select several items from the items and put them into the backpack , Make it put in
* \ The sum of the weights is just S
* \return
*
*/
/** \brief Depth first search analysis
* Knap(index,sum_value) Indicates that at this time, it is right for index Select items , Selected items
* \ Weight is sum_value
* \param
* \return
*
*/
/**< 2th example */
/** \brief
* There is a backpack that can hold items weighing S, existing n Item ,
* \ Ask if it's possible to n Select several items from the items and put them into the backpack , Make it put in
* \ The sum of the weights is just S
* \return
*
*/
/** \brief Depth first search analysis
* Knap(index,sum_value) Indicates that at this time, it is right for index Select items , Selected items
* \ Weight is 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 << " Enter the number of items and backpack capacity :\n";
cin >> n >> s;
cout << " Input " << n<< " The weight of an item :\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";
}
}
边栏推荐
- Talk about the importance of making it clear
- U++ 元数据说明符 学习笔记
- AttributeError: module ‘torch._C‘ has no attribute ‘_cuda_setDevice‘
- Liste des hôtes d'inventaire dans ansible (je vous souhaite des fleurs et de la romance sans fin)
- U++4 接口 学习笔记
- 01机器学习相关规定
- Addressable 预下载
- 指针与数组在函数中输入实现逆序输出
- Operand of null-aware operation ‘!‘ has type ‘SchedulerBinding‘ which excludes null.
- torch optimizer小解析
猜你喜欢
随机推荐
01 machine learning related regulations
Ansible报错:“msg“: “Invalid/incorrect password: Permission denied, please try again.“
Leetcode longest public prefix
Mysql database (basic)
【736. Lisp 语法解析】
JS variable
If you ask me about R code debugging, I will tell you head, STR, help
全链路压测:影子库与影子表之争
ASP. Net MVC - resource cannot be found error - asp Net MVC – Resource Cannot be found error
A line of R code draws the population pyramid
线程池的创建与使用
A simple and beautiful regression table is produced in one line of code~
指针与数组在函数中输入实现逆序输出
torch optimizer小解析
记录一次压测经验总结
Redis如何实现多可用区?
腾讯云数据库公有云市场稳居TOP 2!
Addressable 预下载
最长公共子序列(LCS)(动态规划,递归)
【问道】编译原理