《背包问题》|《背包问题》 动态规划
问题描述：
一切都要从一则故事说起。
话说有一哥们去森林里玩发现了一堆宝石，他数了数，一共有n个。 但他身上能装宝石的就只有一个背包，背包的容量为C。这哥们把n个宝石排成一排并编上号： 0,1,2,…,n-1。第i个宝石对应的体积和价值分别为V[i]和W[i] 。排好后这哥们开始思考： 背包总共也就只能装下体积为C的东西，那我要装下哪些宝石才能让我获得最大的利益呢？
思路分析： 这是动态规划中的经典问题。
核心状态为：dp[i][j] 表示将i件宝物放入容量为j的背包中可以得到的最大价值。
状态转移方程为：dp[i][j]=max( d[i-1][j],dp[i-1][j-w[i]] + v[i])，第一个参数表示不将这一个宝石放入背包中（即，将前i-1个宝石放入背包中的最大的价值），第二个参数表示将这一宝石放入背包中（即，将前i-1个宝石放入背包中的最大的价值加上这个宝石的价值）
编写程序：
递归方法：
show you code：
#include
#include
using namespace std;
int num = 5;
int volume = 10;
int value[]= {0, 8 , 10 , 4 , 5 , 5};
int weight[] = {0, 6 , 4 , 2 , 4 , 3};
int dp[6][11];
int max(int a,int b)
{
return (a>b)? a:b;
}void dp_fun(int n)
{
if(n>5)
{
return;
}
for(int j = volume ;
j >= weight[n] ;
j--)
{
dp[n][j] = max( dp[n-1][j] , dp[n-1][j-weight[n]]+value[n]);
dp_fun(n+1);
}
}int main()
{
memset(dp,0,sizeof(dp));
dp_fun(1);
cout< 【《背包问题》|《背包问题》 动态规划】
两层循环方法：
show you code：
#include
#include
#include
using namespace std;
int num = 5;
int volume = 10;
int value[]= {0, 8 , 10 , 4 , 5 , 5};
int weight[] = {0, 6 , 4 , 2 , 4 , 3};
int dp[6][11];
int max(int a,int b)
{
return (a>b)? a:b;
}
int main()
{
memset(dp,0,sizeof(dp));
for(int i=1;
i<=num;
i++)
{
for(int j=volume;
j>=weight[i];
j--)
{
dp[i][j] = max( dp[i-1][j] , dp[i-1][j-weight[i]] + value[i] );
}
}
cout< 转载于:https://www.cnblogs.com/zhezh/p/3773283.html
推荐阅读
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 《跨界歌手》:亲情永远比爱情更有泪点
- 诗歌:|诗歌: 《让我们举起世界杯，干了！》
- 期刊|期刊 | 国内核心期刊之（北大核心）
- 《魔法科高中的劣等生》第26卷（Invasion篇）发售
- 人间词话的智慧
- 《一代诗人》37期，生活，江南j，拨动心潭的一泓秋水
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术
- 书评——《小行星》