当前位置:网站首页>Knapsack problem (01 knapsack, complete knapsack, dynamic programming)
Knapsack problem (01 knapsack, complete knapsack, dynamic programming)
2022-07-07 05:09:00 【Madness makes freedom】
01 knapsack problem , Two dimensional array for state design
/**< 1th example: */
/** \brief
* 1th solution:
* A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
* \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
* \ How to purchase goods , To maximize profits , Note that at this time, there is only one item
* \ 01 knapsack problem
* \ analysis:
* \ State Design :dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit ;
* \ therefore, Can get dp State transfer equation of :dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
* \ The time complexity and space complexity are both O(n*m);
* \ data : 5 8
3 5 1 2 2
4 5 2 1 3
*/
/**< 1th example: */
/** \brief
* 1th solution:
* A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
* \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
* \ How to purchase goods , To maximize profits , Note that at this time, there is only one item
* \ 01 knapsack problem
* \ analysis:
* \ State Design :dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit ;
* \ therefore, Can get dp State transfer equation of :dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
* \ The time complexity and space complexity are both O(n*m);
* \ data : 5 8
3 5 1 2 2
4 5 2 1 3
*/
/**
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int sum_size,sum_cap;
cout << " Enter the number of items , And the capacity of the backpack :\n";
cin >> sum_size >> sum_cap;
int w[sum_size+1],c[sum_size+1];
int dp[sum_size+1][sum_cap+1];
cout << " Enter the weight of these items :\n";
for(int i=1;i<=sum_size;++i)
cin >> w[i];
cout << " Enter the value of these items :\n";
for(int i=1;i<=sum_size;++i)
cin >> c[i];
for(int i=0;i<=sum_cap;++i)
dp[0][i]=0; //< Boundary design
for(int i=1;i<=sum_size;++i)
{
for(int v=0;v<w[i];++v)
dp[i][v]=dp[i-1][v];// When the remaining capacity of the backpack cannot be filled i When you buy a product , You can only choose this product
for(int v=w[i];v<=sum_cap;++v)
dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
}
int maxn=dp[sum_size][0];
for(int i=1;i<=sum_cap;++i) // In fact, this step should be unnecessary ,dp[sum_size][sum_cap] should
maxn=max(maxn,dp[sum_size][i]);// It's a backpack The maximum profit of the items that can be loaded ;
cout << maxn << endl;
cout << "debeg:\n";
for(auto &a:dp)
{
for(auto b:a)
cout << b << ' ';
cout << endl;
}
cout << "OK:\n" << endl;
int matr[sum_size+1];
int temp=sum_cap;
for(int i=sum_size;i>0;--i) // Select item subscript
{
if(dp[i][temp]==dp[i-1][temp])
matr[i]=0;
else
{
matr[i]=1;
temp-=w[i];
}
}
cout << "max profit: " << maxn << endl;
cout << "choose index:\n";
for(int i=1;i<=sum_cap;++i)
if(matr[i]==1)
cout << i << ' ';
cout << endl;
return 0;
}
*/
01 knapsack problem , One dimensional array for state design
/** \brief
* 2th solution
* A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
* \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
* \ How to purchase goods , To maximize profits , Note that at this time, there is only one item
* \ 01 knapsack problem
* \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit
* \ therefore, Can get dp State transfer equation of :dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i])
* \ The time complexity and space complexity are both O(n*m)
* \ Because of the calculation dp[i+1][] It will only be used dp[i][], And dp[i-1][] irrelevant , So we can
Remove the first dimension , Change the state array into a one-dimensional array ;
But use a one bit array as the status array , Is the subscript of which items cannot be found , There are pros and cons
* \ data : 5 8
3 5 1 2 2
4 5 2 1 3
*/
/** \brief
* 2th solution
* A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
* \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
* \ How to purchase goods , To maximize profits , Note that at this time, there is only one item
* \ 01 knapsack problem
* \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit
* \ therefore, Can get dp State transfer equation of :dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i])
* \ The time complexity and space complexity are both O(n*m)
* \ Because of the calculation dp[i+1][] It will only be used dp[i][], And dp[i-1][] irrelevant , So we can
Remove the first dimension , Change the state array into a one-dimensional array ;
But use a one bit array as the status array , Is the subscript of which items cannot be found , There are pros and cons
* \ data : 5 8
3 5 1 2 2
4 5 2 1 3
*/
//#include <iostream>
//#include <cstring>
//using namespace std;
//
//int main()
//{
// int sum_size,sum_cap;
// cout << " Enter the number of items , And the capacity of the backpack :\n";
// cin >> sum_size >> sum_cap;
// int w[sum_size+1],c[sum_size+1];
// int dp[sum_cap+1];
// cout << " Enter the weight of these items :\n";
// for(int i=1;i<=sum_size;++i)
// cin >> w[i];
// cout << " Enter the value of these items :\n";
// for(int i=1;i<=sum_size;++i)
// cin >> c[i];
//
// memset(dp,0,sizeof(dp)); /**< Boundary design */
// for(int i=1;i<=sum_size;++i)
// {
// for(int v=w[i];v<=sum_cap;++v) /**< Error code , It should be recursion from right to left */
// dp[v]=max(dp[v],dp[v-w[i]]+c[i]); /**< It's all about v The element on the right is irrelevant , The element on the right is used for recursion dp[i+1][] */
// } /**< If v Recursion from left to right , It will affect the value of the elements recursed in the next column */
//
// int maxn=dp[0];
// for(int i=1;i<=sum_cap;++i)
// maxn=max(maxn,dp[i]);
//
// cout << "error answer : " << maxn << endl;
//
// cout << "debeg:\n";
// for(auto &a:dp)
// cout << a << ' ';
// cout << endl;
//
// for(int i=0;i<=sum_cap;++i)
// dp[i]=0; /**< Boundary design */
// for(int i=1;i<=sum_size;++i) /**< because dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]) */
// {
// for(int v=sum_cap;v>=w[i];--v) /**< It's all about v The element on the right is irrelevant , The element on the right is used for recursion dp[i+1][] */
// dp[v]=max(dp[v],dp[v-w[i]]+c[i]);/**< If v Recursion from left to right , It will affect the value of the elements recursed in the next column */
// }
//
// maxn=dp[0];
// for(int i=1;i<=sum_cap;++i)
// maxn=max(maxn,dp[i]); /** but dp[sum_cap] Is it the maximum value ? I feel like , But there is a certain doubt in my heart */
// cout << " true answer: \n" << maxn << endl;
//
// cout << "debeg:\n";
// for(auto &a:dp)
// cout << a << ' ';
// cout << endl;
// return 0;
//}
Complete knapsack problem , Two dimensional array for state design
/**< 2th example: */
/** \brief
* 1th solution
* A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
* \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
* \ How to purchase goods , To maximize profits , Note that there are countless pieces of each item at this time
* \ Complete knapsack problem
* \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit
* \ therefore, Can get dp State transfer equation of :dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
* \ The time complexity and space complexity are both O(n*m)
* \ data : 5 8
3 5 1 2 2
4 5 2 1 3
*/
/**
5 9
3 5 1 2 2
4 5 2 5 3
*/
/**< 2th example: */
/** \brief
* 1th solution
* A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
* \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
* \ How to purchase goods , To maximize profits , Note that there are countless pieces of each item at this time
* \ Complete knapsack problem
* \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit
* \ therefore, Can get dp State transfer equation of :dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
* \ The time complexity and space complexity are both O(n*m)
* \ data : 5 8
3 5 1 2 2
4 5 2 1 3
*/
/**
5 9
3 5 1 2 2
4 5 2 5 3
*/
/**
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int sum_size,sum_cap;
cout << " Enter the number of items , And the capacity of the backpack :\n";
cin >> sum_size >> sum_cap;
int w[sum_size+1],c[sum_size+1];
int dp[sum_size+1][sum_cap+1];
cout << " Enter the weight of these items :\n";
for(int i=1;i<=sum_size;++i)
cin >> w[i];
cout << " Enter the value of these items :\n";
for(int i=1;i<=sum_size;++i)
cin >> c[i];
for(int i=0;i<=sum_cap;++i)
dp[0][i]=0; // Boundary design
for(int i=1;i<=sum_size;++i)
{
for(int v=0;v<w[i];++v)
dp[i][v]=dp[i-1][v]; // When the remaining capacity of the backpack cannot be filled i When you buy a product , You can only choose this product
for(int v=w[i];v<=sum_cap;++v)
dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i]);
}
int maxn=dp[sum_size][0];
for(int i=1;i<=sum_cap;++i) // In fact, this step should be unnecessary ,dp[sum_size][sum_cap] It should be a backpack
maxn=max(maxn,dp[sum_size][i]);// The maximum profit of the items that can be loaded
cout << maxn << endl;
cout << "debeg:\n";
for(auto &a:dp)
{
for(auto b:a)
cout << b << ' ';
cout << endl;
}
int matr[sum_size+1];
int temp=sum_cap;
for(int i=sum_size;i>0;--i) // Select item subscript
{
if(dp[i][temp]==dp[i-1][temp])
matr[i]=0;
else
{
int num=0;
while(dp[i][temp]-dp[i][temp-w[i]*(num+1)]==c[i]*(num+1))
{ //< According to the state transfer equation ,dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
++num; //< When dp[i][v]!=dp[i-1][v] when , Must have chosen the first i Item , But how many pieces have you chosen ,
if(temp-w[i]*(num+1)<0) //< from dp[i][v-w[i]] decision , When their difference equals c[i] when , Then add up one
break; //< Keep going , Until the above conditions are not met
}
matr[i]=num;
temp-=w[i]*num;
}
}
cout << "max profit: " << maxn << endl;
cout << "choose index:\n";
for(int i=1;i<=sum_size;++i)
if(matr[i]!=0)
cout << i << "th choose " << matr[i] << " pair\n" ;
return 0;
}
*/
Complete knapsack problem , One dimensional array for state design
/**< 2th example: */
/** \brief
* 2th solution
* A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
* \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
* \ How to purchase goods , To maximize profits , Note that there are countless pieces of each item at this time
* \ Complete knapsack problem
* \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit
* \ therefore, Can get dp State transfer equation of :dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
* \ The time complexity and space complexity are both O(n*m)
* \ Because of the calculation dp[i+1][] It will only be used dp[i][], And dp[i-1][] irrelevant , So we can
Remove the first dimension , Change the state array into a one-dimensional array
* \ data : 5 8
3 5 1 2 2
4 5 2 1 3
*/
/**< 2th example: */
/** \brief
* 2th solution
* A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
* \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
* \ How to purchase goods , To maximize profits , Note that there are countless pieces of each item at this time
* \ Complete knapsack problem
* \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit
* \ therefore, Can get dp State transfer equation of :dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
* \ The time complexity and space complexity are both O(n*m)
* \ Because of the calculation dp[i+1][] It will only be used dp[i][], And dp[i-1][] irrelevant , So we can
Remove the first dimension , Change the state array into a one-dimensional array
* \ data : 5 8
3 5 1 2 2
4 5 2 1 3
*/
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int sum_size,sum_cap;
cout << " Enter the number of items , And the capacity of the backpack :\n";
cin >> sum_size >> sum_cap;
int w[sum_size+1],c[sum_size+1];
int dp[sum_cap+1];
cout << " Enter the weight of these items :\n";
for(int i=1;i<=sum_size;++i)
cin >> w[i];
cout << " Enter the value of these items :\n";
for(int i=1;i<=sum_size;++i)
cin >> c[i];
memset(dp,0,sizeof(dp)); //< Boundary design
for(int i=1;i<=sum_size;++i)
{
for(int v=sum_cap;v>=w[i];--v) //< Error code , It should be recursion from left to right
dp[v]=max(dp[v],dp[v-w[i]]+c[i]); //< v It should be recursive from left to right , because dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
} //< Calculation dp[i][v] The element on the left will be used , Calculate the one on the left before each calculation
int maxn=dp[0];
for(int i=1;i<=sum_cap;++i)
maxn=max(maxn,dp[i]);
cout << "error answer : " << maxn << endl;
cout << "debeg:\n";
for(auto &a:dp)
cout << a << ' ';
cout << endl;
cout << "OK: \n\n";
memset(dp,0,sizeof(dp)); //< Boundary design
for(int i=1;i<=sum_size;++i)
{
for(int v=w[i];v<=sum_cap;++v) //< v It should be recursive from left to right , because dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
dp[v]=max(dp[v],dp[v-w[i]]+c[i]);//< Calculation dp[i][v] The element on the left will be used , Calculate the one on the left before each calculation
}
maxn=dp[0];
for(int i=1;i<=sum_cap;++i) //< In fact, this step should be unnecessary ,dp[sum_cap] It should be a backpack
maxn=max(maxn,dp[i]);//< The maximum profit of the items that can be loaded
cout << "true answer : " << maxn << endl;
cout << "debeg:\n";
for(auto &a:dp)
cout << a << ' ';
cout << endl;
return 0;
}
边栏推荐
- 记录一次压测经验总结
- AttributeError: module ‘torch._C‘ has no attribute ‘_cuda_setDevice‘
- STM32F103实现IAP在线升级应用程序
- ThinkPHP关联预载入with
- If you‘re running pod install manually, make sure flutter pub get is executed first.
- The sooner you understand the four rules of life, the more blessed you will be
- If you‘re running pod install manually, make sure flutter pub get is executed first.
- Gavin teacher's perception of transformer live class - rasa project actual combat e-commerce retail customer service intelligent business dialogue robot microservice code analysis and dialogue experim
- 线程同步的两个方法
- U++ 元数据说明符 学习笔记
猜你喜欢
Monitoring cannot be started after Oracle modifies the computer name
为什么很多人对技术债务产生误解
拿到PMP认证带来什么改变?
Markdown编辑器
批量归一化(标准化)处理
How to design API interface and realize unified format return?
sublime使用技巧
torch optimizer小解析
Inventory host list in ansible (I wish you countless flowers and romance)
The sooner you understand the four rules of life, the more blessed you will be
随机推荐
【ArcGIS教程】专题图制作-人口密度分布图——人口密度分析
Factor analysis r practice (with R installation tutorial and code)
AttributeError: module ‘torch._ C‘ has no attribute ‘_ cuda_ setDevice‘
Stm32f103ze+sht30 detection of ambient temperature and humidity (IIC simulation sequence)
Leetcode(46)——全排列
Servicemesh mainly solves three pain points
Appium practice | make the test faster, more stable and more reliable (I): slice test
U++4 接口 学习笔记
When knative meets webassembly
Timer创建定时器
Sublime tips
《五》表格
ThinkPHP关联预载入with
3GPP信道模型路损基础知识
最全常用高数公式
5G VoNR+之IMS Data Channel概念
App embedded H5 --- iPhone soft keyboard blocks input text
How to design API interface and realize unified format return?
使用Thread类和Runnable接口实现多线程的区别
Weebly mobile website editor mobile browsing New Era