大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
动态规划题目背包问题(例题分析)
物品编号 1 2 3 4
物品体积 2 3 4 5
物品价值 3 4 5 6
求容积为8的背包能装的最大价值为多少?
解题思路
动态规划解题步骤
1)确定状态
注意: 动态规划一般要开数组,首先要明确数组的每个元素所代表的意义。
确定状态需要两个意识:(1)最后一步(2)子问题。
2)转移方程的确定
3)初始化条件和边界情况
注意:初始状态大部分都是为零,用转移方程算不出来的才需要手动定义状态。
4)计算顺序
注意:一般的计算顺序是从小到大,从上到下从左到右(二维)。
本题的状态转移方程很容易就可以得出来是f[i][j]=max(f[i-1][j], f[i-1][j-vol[i]]+val[i])
这里有两个方面需要考虑,第一个是你准备将第i件物品放入,第二是你不准备放入。所以你首先需要比较体积大小,然后比较物品价值。f[i-1][j]是你没有放入物品时的情况,f[i-1][j-vol[i]]+val[i]是你要放入物品时,计算当前物品和剩余空间价值的和。然后求他们的最大值max。
本题还提供了back(),是求解到底去了哪几件物品,是背包问题的回溯。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
using namespace std;
int val[]={
0,3,4,5,6};
int vol[]={
0,2,3,4,5};
int f[5][9];
bool flag[5]={
true};
//背包的容积为8
//物品编号1,2,3,4
//物品容积2,3,4,5
//物品体积3,4,5,6
int maxvalue(){
for(int i=0; i<=4; i++){
for(int j=0; j<=8; j++){
if(i==0 || j==0){
f[i][j]=0;
}else{
if(vol[i]<=j)
f[i][j]=max(f[i-1][j], f[i-1][j-vol[i]]+val[i]);
else{
f[i][j]=f[i-1][j];
}
}
}
}
}
int back(int i, int j){
if(i==0){
for(int i=1; i<5; i++){
if(flag[i]) cout<<i<<" ";
}
}
if(f[i][j]==f[i-1][j]){
back(i-1,j);
}
else if(f[i][j]==f[i-1][j-vol[i]]+val[i]){
flag[i]=true;
back(i-1,j-vol[i]);
}
}
int main(){
maxvalue();
for(int i=0; i<=4; i++){
for(int j=0; j<=8; j++){
printf("%4d",f[i][j]);
}
cout<<endl;
}
back(4,8);
return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164411.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...