动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。
比如01背包问题。
/* 一个旅行者有一个最多能用M公斤的背包,现在有N件物品,
它们的重量分别是W1,W2,...,Wn,
它们的价值分别为P1,P2,...,Pn.
若每种物品只有一件求旅行者能获得最大总价值。
输入格式:
M,N
W1,P1
W2,P2
......
输出格式:
X
*/
因为背包最大容量M未知。所以,我们的程序要从1到M一个一个的试。比如,开始任选N件物品的一个。看对应M的背包,能不能放进去,如果能放进去,并且还有多的空间,则,多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢?看下表。
测试数据:
10,3
3,4
4,5
5,6
c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.
这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候,最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候,最佳方案还是上一排的最价方案c为4.而背包容量为5的时候,则最佳方案为自己的重量5.背包容量为7的时候,很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)
从以上最大价值的构造过程中可以看出。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程。
下面给出我们第五次个人赛时出的一道题:
Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
//基础01背包问题,v容量的包,每个物品权值和容量已知求包能装的最大总权值和。
//f[i][j]表示对于前i个物品,包的容量为j时最大能装的权值和,当然转移的时候对于当前物品
//只有装和不装两种选择,如果不装则由f[i-1][j],如果装则由f[i-1][j-vol[i]]转移而来。
#include<iostream>
using namespace std;
#define IN(x) scanf("%d",&x)
#define max(x,y) x>y?x:y
int value[1009],volume[1009];
int f[1001][1001];
int main()
{
int cnt,n,v,i,j;
IN(cnt);
while(cnt--)
{
IN(n);IN(v);
for(i = 1; i <= n; i ++) //注意,这边得空出一位来,wa了两次了
IN(value[i]);
for(i = 1; i <= n; i ++)
IN(volume[i]);
memset(f,0,sizeof(f));
for(i = 1; i <= n; i ++)
for(j = 0; j <= v; j ++)
{
if(volume[i] <= j)
f[i][j] = max(f[i-1][j],f[i-1][j-volume[i]]+value[i]);
else
f[i][j] = f[i-1][j];
}
printf("%d\n",f[i-1][j-1]);
}
return 0;
}
另外,这也可以用一维数组来简化代码。f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下:
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][vc[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v 的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题:完全背包问题 最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。
下面给出本题的一维数组的解法。
#include<iostream>
using namespace std;
#define IN(x) scanf("%d",&x)
#define max(x,y) x>y?x:y
int value[1009],volume[1009];
int f[1001];
int main()
{
int cnt,n,v,i,j;
IN(cnt);
while(cnt--)
{
IN(n);IN(v);
for(i = 0; i < n; i ++)
IN(value[i]);
for(i = 0; i < n; i ++)
IN(volume[i]);
memset(f,0,sizeof(f));
for(i = 0; i < n; i ++)
for(j = v; j >= 0; j --)
{
if(volume[i] <= j)
f[j] = max(f[j],f[j-volume[i]]+value[i]);
}
printf("%d\n",f[v]);
}
return 0;
}
分享到:
相关推荐
### 0/1背包问题分支界限算法C++实现解析 #### 背包问题概述 背包问题(Knapsack Problem)是计算机科学与数学中一个经典的优化问题,它描述了一个带有固定容量的背包如何选择一组物品,使得背包内的物品价值总和...
在计算机科学中,0/1 背包问题是一个经典的组合优化问题,属于动态规划的应用范畴。这个问题的基本设定是:有一个背包,它的容量有限,以及一系列物品,每个物品都有一个重量和一个价值。目标是选择物品放入背包中,...
虽然题目标签标注的是“分治算法”,但0/1背包问题更常采用**动态规划**方法求解。这是因为分治算法通常适用于可分解成独立子问题的情况,而0/1背包问题中的每个物品的选择都依赖于之前的选择,不适合直接使用分治法...
有比较详细的0-1背包动态规划的讲解 有实例可以帮助大家更好的熟悉动态规划问题的理解
### 0-1背包问题分支界限法求解——C语言实现 #### 一、背景介绍 在计算机科学中,背包问题是一类优化问题的经典案例,它涉及到如何在满足一定约束条件下(例如背包的最大承重),从一系列物品中选择最优组合以达到...
### 01背包问题动态规划详解及其学习意义 #### 一、01背包问题概述 01背包问题作为计算机科学领域中的一个经典问题,属于组合优化问题的一种。该问题的基本形式如下:假设我们有一个背包,这个背包的最大承重为W...
1D/1D动态规划,即状态数和每个状态决策量均为O(n)级别的动态规划问题。直接求解这类问题通常会导致O(n^2)的时间复杂度,但通过对问题的深入理解和巧妙设计,大多数情况下可以将其优化至O(nlogn)甚至O(n)的时间...
### 用动态规划法与回溯法实现0_1背包问题的比较 #### 一、引言 0-1背包问题是一种经典的组合优化问题,在实际应用中有着广泛的背景,例如资源分配、投资组合等问题都可以抽象成背包问题的形式。本文旨在通过分析...
"0-1背包详解" "0-1"背包问题是计算机科学中的一种经典问题,它是指在有限的背包空间中,如何选择物品使得总的价值最大化。解决这个问题有多种方法,包括贪心算法和动态规划算法。 贪心算法是指在每一步选择当前看...
### 01背包问题(动态规划法) #### 一、问题描述 01背包问题是一种经典的组合优化问题,在计算机科学领域具有重要的应用价值,尤其是在算法竞赛中极为常见。假设我们有一个背包,其最大载重量为 \( m \),同时有一...
### 0-1背包问题的C语言实现:递归与动态规划 #### 一、问题背景及概述 0-1背包问题是计算机科学中一个经典的组合优化问题,它涉及到如何从一组物品中选择部分物品装入背包,使得背包的总价值最大,同时不超过背包...
### 动态规划背包问题讲解 #### 一、动态规划概览 动态规划(Dynamic Programming,简称DP)是一种在计算机科学与数学优化中常见的算法思想。它主要用于解决那些具有重叠子问题和最优子结构的问题。动态规划的核心...
解决0-1背包问题常用的方法是动态规划。动态规划的核心思想是通过构建子问题的解决方案来解决原问题。具体到0-1背包问题,我们可以定义状态dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。 #### 三...
动态规划是解决0-1背包问题的常用方法,通过构建一个二维数组来记录每个阶段的最大价值,状态转移方程为f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]},其中f[i][v]代表考虑前i件物品,在容量为v的背包中可以获得的...
通过对不同类型的背包问题的分析,我们可以看到动态规划的强大之处。无论是0/1背包、完全背包还是多重背包,通过合理地定义状态、构造状态转移方程并运用一些优化技巧,都可以有效地解决这些问题。掌握这些基本的...
### 基于Visual C++的0-1背包问题的动态规划算法 #### 摘要 0-1背包问题是一种经典的组合优化问题,在计算机科学领域有着广泛的应用,尤其是在资源分配、任务调度等方面。该问题的基本形式是:给定一组物品(每个...
### 分支限界法实现0-1背包问题 #### 一、基础知识介绍 **0-1背包问题**是一种经典的组合优化问题,在计算机科学与运筹学领域有着广泛的应用。问题可以表述为:给定一系列物品,每个物品都有一个重量和一个价值;...
01背包问题与分数背包问题是计算机科学中优化问题的经典实例,尤其在...在学习过程中,通过分析和实践如"01背包问题和分数背包问题详解(动态规划和贪心算法).docx"这样的文档,可以深入理解这些概念并加强实战技能。
动态规划问题通常分为两类:确定性问题和概率性问题。其中,确定性问题如斐波那契数列、最长公共子序列等,概率性问题则涉及随机决策过程。 2. **动态规划的五要素** - 状态:定义问题的每一个决策阶段; - 决策...