详细页面:http://www.verydemo.com/demo_c92_i63400.html
背包问题(DP、回溯)
#include"map"
using namespace std ;
class Knapsack{
public :
double c ;//Knapsack capacity
int n ; // item numbers
double w [1000] ;// Item weight array
double p [1000] ;//item value array
double cw ;//current weight
double cp ;// current value
double bestp; // current best value
double setdata ( )
{
cw = 0.0 ;
cp = 0.0;
bestp =0 ;
}
void backtrack(int i)
{
if ( i > n )
{
bestp = cp ;
// 为什么不用和前一个进行比较就进行跟新呢?者主要得利域贪心算法的好处,。进入左子树时不需要计算上界,因为其上界以其父结点的上界相同
return ;//to Leaf node
}
//sort child tree
if ( cw + w [i] <= c )
{
//into left child tree
cw += w[i];
cp+=p[i];
backtrack( i + 1 );
cw -= w [ i ] ;
cp -= p[i] ;
}
if(bound( i+1 ) > bestp )
backtrack( i + 1 ) ; //into light child tree
}
//calculate up bound
double bound( int i )
{
//calculate up bound
double cleft = c - cw ;//residual capacity
double bound = cp ;
//With items unit weight value decreasing order load items
while ( i <= n && w[i] <= cleft )
{
cleft -= w[i];
bound += p[i];
i++;
}
//Backpack being filled with
if ( i <= n )
{
bound += p[i] / w[i]* cleft ;
}
return bound ;
}
};
int main()
{
Knapsack kk ,kk_1 ;
multimap< double ,int > m ;
multimap<double ,int >::reverse_iterator t;
int n;
int T ;
int j=1 ;
cin>>T;
while(T>0)
{
cin>>kk.n;
cin>>kk.c;
int i =1 ;
while(i<=kk.n)
{
cin>>kk.w[i];
cin>>kk.p[i];
m.insert(pair<double,int >(kk.p[i]/kk.w[i],i));
i++;
}
//sort the data
n=kk.n;
i = 1 ;
t = m.rbegin();
while(t!=m.rend())
{
kk_1.w[i] = kk.w[t->second];
kk_1.p[i] = kk.p[t->second];
// cout<<":"<<kk_1.w[i]<<" "<<kk_1.p[i];
i++;
++t;
}
m.clear();
kk_1.c = kk.c ;
kk_1.n = kk.n;
kk_1.setdata();
kk_1.backtrack(1);
int b =kk_1.bestp;
cout<<b<<endl;
T--;
}
return 0 ;
}
算法设计例题:背包问题(DP、回溯)
memory limit: 65536KB time limit: 500MS
accept: 7 submit: 24
Description
Input
Output
Sample Input
Sample Output
#include"iostream"
#include"algorithm"#include"map"
using namespace std ;
class Knapsack{
public :
double c ;//Knapsack capacity
int n ; // item numbers
double w [1000] ;// Item weight array
double p [1000] ;//item value array
double cw ;//current weight
double cp ;// current value
double bestp; // current best value
double setdata ( )
{
cw = 0.0 ;
cp = 0.0;
bestp =0 ;
}
void backtrack(int i)
{
if ( i > n )
{
bestp = cp ;
// 为什么不用和前一个进行比较就进行跟新呢?者主要得利域贪心算法的好处,。进入左子树时不需要计算上界,因为其上界以其父结点的上界相同
return ;//to Leaf node
}
//sort child tree
if ( cw + w [i] <= c )
{
//into left child tree
cw += w[i];
cp+=p[i];
backtrack( i + 1 );
cw -= w [ i ] ;
cp -= p[i] ;
}
if(bound( i+1 ) > bestp )
backtrack( i + 1 ) ; //into light child tree
}
//calculate up bound
double bound( int i )
{
//calculate up bound
double cleft = c - cw ;//residual capacity
double bound = cp ;
//With items unit weight value decreasing order load items
while ( i <= n && w[i] <= cleft )
{
cleft -= w[i];
bound += p[i];
i++;
}
//Backpack being filled with
if ( i <= n )
{
bound += p[i] / w[i]* cleft ;
}
return bound ;
}
};
int main()
{
Knapsack kk ,kk_1 ;
multimap< double ,int > m ;
multimap<double ,int >::reverse_iterator t;
int n;
int T ;
int j=1 ;
cin>>T;
while(T>0)
{
cin>>kk.n;
cin>>kk.c;
int i =1 ;
while(i<=kk.n)
{
cin>>kk.w[i];
cin>>kk.p[i];
m.insert(pair<double,int >(kk.p[i]/kk.w[i],i));
i++;
}
//sort the data
n=kk.n;
i = 1 ;
t = m.rbegin();
while(t!=m.rend())
{
kk_1.w[i] = kk.w[t->second];
kk_1.p[i] = kk.p[t->second];
// cout<<":"<<kk_1.w[i]<<" "<<kk_1.p[i];
i++;
++t;
}
m.clear();
kk_1.c = kk.c ;
kk_1.n = kk.n;
kk_1.setdata();
kk_1.backtrack(1);
int b =kk_1.bestp;
cout<<b<<endl;
T--;
}
return 0 ;
}
相关推荐
背包问题通常可以通过动态规划、贪心算法或者回溯算法来解决。下面是一个简单的动态规划解法的伪代码示例,用于解决0-1背包问题: ```plaintext 函数 knapsack(weights[], values[], capacity): 创建一个二维数组 ...
回溯法解决01背包问题的原理和实现步骤: 定义一个数组dp,其中dp[i][j]表示在前i个物品中选,总重量不超过j的条件下,能够获得的最大价值。 初始化dp数组的所有元素为0。 定义一个递归函数backtrack,它有两个参数...
解决背包问题的常见方法包括动态规划、贪心算法和回溯算法。 以下是用动态规划解决0/1背包问题的示例: ```python def knapsack(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for ...
dfs回溯法解决0-1背包的问题。 对比dp方法,dfs可以减小空间复杂度。
再看代码: pass着色问题背包问题推荐阅读0-1背包完全背包回溯问题单调栈问题常见DP问题LCS编辑距离寻路问题推荐阅读特殊图的寻路一般图的寻路常见分治算法图相关算法遍历的非递归算法树的遍历图的遍历知识管理 ...
ACM初步,算法初步,递推求解,分治策略,DP1-2,0-1背包,贪心算法,回溯法,分支限界法,计算几何,母函数及其应用, 二分图及其应用, 特殊的数, 数论算法, 网络流, 图的着色问题与排队论, 大数问题, 组合数学, 其他
树] Java4 不适用 简单[位操作] Java5 不适用 中[背包DP,DP] Java6 不适用中[] Java7 不适用 中[DFS,DP,状态DP,树] Java8 不适用 中[DFS,树] Java9 不适用 中[背包DP,DP] Java10 不适用简单[二分查找] Java11 ...
【背包DP、DP】 Java 6 不适用 中等的 [] Java 7 不适用 中等的 [DFS、DP、状态DP、树] Java 8 不适用 中等的 [DFS,树] Java 9 不适用 中等的 【背包DP、DP】 Java 10 不适用 简单的 【二分查找】 Java 11 不适用 ...
Leetcode经典01背包 LeetCode-2020 马上进入2020找实习冲刺阶段,我决定以天为单位,记录每天做的LeetCode习题,方便后期整理。 C++文档神器推荐:cppreference.chm 1 LeetCode刷题记录(每日更新) :calendar: 更新...
leetcode 2 leetcode-cpp-实践 包括问题陈述、解决方案、运行时间和复杂性分析。 动态安全协议 ...两约束背包问题 信息系统 DP + 树 数字 数数 递归 可能性 游戏 尼姆游戏 石头游戏 井字游戏 DFS + 记忆 动态
背包 (硬币变化) multi_var_DP 传统_DP (缓存+DP) (缓存+DP) 差异_DP 回溯 分而治之 两个指针 (re.sub) BFS (BFS) (最低适用条件) 分布式文件系统 传统_DFS (如何找到树的中间) (DP + DFS + 记忆) ...
背包问题 分区问题 棒材切割 硬币变化问题 断字问题 第二节贪心算法 活动选择问题 图形的贪婪着色 有期限的作业排序 霍夫曼编码 MST 的 Kruskal 算法 MST 的 Prim 算法 单源最短路径 第 3 节 图表 BFS 分布式文件...
背包(dp,dfs(回溯),bfs,最佳优先搜索) 4/13动态编程2 问题 : J1871 , J2191 , S1263 (S1263 floyd,dijkstra)(使用S1263优先级队列来解决) 所有配对最短的(floyd,dijkstra) LIS 编辑距离 4/14...
树和图(遍历,DP) 算法/编码模式 点击展开! 滑动窗口(Acquire-Settle-Release Method) 两个指针 快慢指针 合并间隔(Linesweep Technique) 循环排序 链表的就地反转 BFS,DFS和拓扑排序 2 堆 二分搜索(保存和...
leetcode计算机刷墙 主要包括以下内容 LeetCode刷题笔记 专题学习笔记 另一个目的也是怕笔记丢了,毕竟typora虽然强大,但不能云端存储。 一、Docker 二、Java相关 ...17、背包问题 ...... 陆续更新中
leetcode 凑硬币 算法和数据结构 数据结构 数组 堆栈和队列 数组出列 数组堆栈 链接堆栈 优先队列 ...二叉搜索树(平衡和不平衡)...背包问题 最大化表达式的值 分区问题 | 动态规划解决方案 回溯O(2^n)空间 O(1) DP时间 O
leetcode 316 LeetCode、剑指Offer刷题笔记(C++实现) ...树形DP 0-1背包 [474_一和零] 完全背包 [322_零钱兑换] [518_零钱兑换ii] 回溯 字典树(Trie) 树的遍历 二叉查找树 并查集 前缀和 剑指Offer