/*在一固定容积为C的背包内装入N件物品,
物品的体积为:w1,w2,-----wn;
价值为:v1,v2,------vn;
求能装物品的最大价值。*/
这类问题的决策是:第N件物品放或者不放;
由此可以写出动态转移方程:
我们用n[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值
n[i][j]=max{n[i-1][j-Wi]+v[i] , f[i-1,j]} 注(j>=Wi);
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为c的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为c的背包中”,价值为v[i];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为c-w[i]的背包中”,此时能获得的最大价值就是n[c-w[i]]再加上通过放入第i件物品获得的价值v[i]。
#include<stdio.h>
int n[10000][10000];
int main()
{
int T,N,w[10000],v[10000],c,c1,i,j;
scanf("%d",&T);
while(T--)
{
printf("请输入物品个数:");
scanf("%d",&N);
printf("请输入每个物品的重量和价值:\n");
for(i=1;i<=N;i++)
scanf("%d%d",&w[i],&v[i]);
printf("请输入背包容积:");
scanf("%d",&c);
for(i=0;i<=c;i++)
n[0][i]=0;
for(j=0;j<=c;j++)
{
for(i=1;i<=N;i++)
{
if(j==0)
n[i][j]=0;
if(w[i]>j)
{
if(i==1)
n[i][j]=0;
else
n[i][j]=n[i-1][j];
}
else
{
if(i==1)
n[i][j]=v[i];
else
{
c1=j-w[i];
n[i][j]=n[i-1][j]>(v[i]+n[i-1][c1])?(n[i-1][j]):(v[i]+n[i-1][c1]);
}
}
}
}
printf("%d\n",n[N][c]);
}
return 0;
}
物品的体积为:w1,w2,-----wn;
价值为:v1,v2,------vn;
求能装物品的最大价值。*/
这类问题的决策是:第N件物品放或者不放;
由此可以写出动态转移方程:
我们用n[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值
n[i][j]=max{n[i-1][j-Wi]+v[i] , f[i-1,j]} 注(j>=Wi);
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为c的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为c的背包中”,价值为v[i];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为c-w[i]的背包中”,此时能获得的最大价值就是n[c-w[i]]再加上通过放入第i件物品获得的价值v[i]。
#include<stdio.h>
int n[10000][10000];
int main()
{
int T,N,w[10000],v[10000],c,c1,i,j;
scanf("%d",&T);
while(T--)
{
printf("请输入物品个数:");
scanf("%d",&N);
printf("请输入每个物品的重量和价值:\n");
for(i=1;i<=N;i++)
scanf("%d%d",&w[i],&v[i]);
printf("请输入背包容积:");
scanf("%d",&c);
for(i=0;i<=c;i++)
n[0][i]=0;
for(j=0;j<=c;j++)
{
for(i=1;i<=N;i++)
{
if(j==0)
n[i][j]=0;
if(w[i]>j)
{
if(i==1)
n[i][j]=0;
else
n[i][j]=n[i-1][j];
}
else
{
if(i==1)
n[i][j]=v[i];
else
{
c1=j-w[i];
n[i][j]=n[i-1][j]>(v[i]+n[i-1][c1])?(n[i-1][j]):(v[i]+n[i-1][c1]);
}
}
}
}
printf("%d\n",n[N][c]);
}
return 0;
}
发表评论
-
杭电1162 最小生成树问题
2012-07-27 15:15 857题目链接:http://acm.hdu.edu.cn/show ... -
杭电1596 迪杰特斯拉算法的应用
2012-07-25 20:47 1064题目 Problem Description XX星球有很多 ... -
杭电2680 迪杰特斯拉算法的应用
2012-07-25 20:43 1045题目描述: Problem Description: One ... -
杭电1272
2012-07-18 15:13 829这道题主要就是判断一下有没有环,还有就是节点数减去边数等于1, ... -
杭电2544 最短路径
2012-07-17 17:31 858Problem Description 在每年的校赛里,所有进 ... -
迪杰斯特拉(Dijkstra)算法
2012-07-17 16:07 1462迪杰斯特拉算法 迪杰斯特拉(Dijkstra)算法思想 ... -
杭电acm部分题目分类
2012-07-07 16:38 3423注:DP代表动态规划 1001 这个就不用说了吧 ... -
动态规划之背包问题
2012-07-07 16:12 0/*在一固定容积为C的背包内装入N件物品, 物品的体积为:w1 ... -
背包问题
2012-07-07 10:44 0决策是:第N件物品放或者不放; 由此可以写出动态转移方 ... -
杭电1003代码
2012-07-07 10:24 938#include<stdio.h> int mai ... -
动态规划
2012-07-07 10:21 748动态规划算法 一、基本 ...
相关推荐
01背包问题是动态规划的经典模型之一,它可以用于解决许多实际问题,例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题。 动态规划算法的基本思想是将待求解的问题分解成若干个子问题,然后从这些子...
本篇文章将深入探讨这两个背包问题以及如何使用动态规划来解决它们。 **0-1背包问题**: 0-1背包问题是一个典型的优化问题,它假设有一个容量有限的背包(背包容量为W),以及一系列物品,每件物品都有一个重量w[i]...
在本场景中,我们关注的是使用C语言实现动态规划解决背包问题。背包问题是一类经典的组合优化问题,通常涉及到在给定容量的背包中选择物品以最大化价值或满足特定目标。 背包问题的基本形式可以描述为:给定一组...
动态规划的背包问题,是不是一度让你很苦恼?不急,有了这个PPT,能让你做背包问题易如反掌。
动态规划是一种强大的算法思想,广泛应用于解决复杂优化问题,其中包括著名的背包问题。在这个问题中,我们通常面临一个有限容量的背包和一系列物品,每个物品都有自己的重量和价值。目标是选择物品,使得装入背包的...
《背包九讲》是关于背包问题和动态规划算法的一份深度学习资料,它涵盖了完全背包、0-1背包以及多重背包等经典的优化问题。在计算机科学和算法设计中,动态规划是一种有效解决这类问题的方法,它通过将大问题分解为...
在计算机算法设计与分析中,动态规划法是解决背包问题的常用方法之一。所谓背包问题,是指在有限的背包容量下,如何选择物品来达到最大价值的问题。在本文中,我们将对动态规划法求解0-1背包问题的改进算法进行详细...
本文实例讲述了C++动态规划之背包问题解决方法。分享给大家供大家参考。具体分析如下: 问题描述: 背包的最大容量为W,有N件物品,每件物品重量为w,价值为p,怎样选择物品能使得背包里的物品价值最大? 输入: 10 3...
0-1背包问题是一个经典的优化问题,主要涉及动态规划算法的运用。在这个实验报告中,学生使用Java语言解决了一个0-1背包问题的实例。以下是关于这个问题和解决方案的详细解释。 一、问题描述: 0-1背包问题的核心是...
01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1...动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。
本资源为 MATLAB 代码,代码中用动态规划解决了0-1背包问题。具体问题为:物品价值:v=[90 75 83 32 56 31 21 43 14 65 12 24 42 17 60];物品重量:w=[30 27 23 24 21 18 16 14 12 10 9 8 6 5 3]; 背包容量:120。...
### 动态规划背包问题讲解 #### 一、动态规划概览 动态规划(Dynamic Programming,简称DP)是一种在计算机科学与数学优化中常见的算法思想。它主要用于解决那些具有重叠子问题和最优子结构的问题。动态规划的核心...
动态规划是一种有效的算法设计策略,尤其适用于解决具有重叠子问题和最优子结构的问题,而0-1背包问题就是这种策略的一个典型应用。0-1背包问题是一个经典的组合优化问题,它源自实际生活中的资源分配问题,比如在...
动态规划背包问题.cpp
在提供的压缩包文件"Knapsack"中,可能包含了用某种编程语言实现的回溯法或动态规划法解01背包问题的源代码。由于代码未编译完成,你需要自行完成编译和运行,以验证和理解算法的具体实现。在调试和运行代码时,注意...
对于0-1背包问题,动态规划的解决方案通常包括以下步骤: 1. 初始化:创建一个二维数组`dp`,其中`dp[i][j]`表示在前`i`件物品中选择总重量不超过`j`的物品所能得到的最大价值。初始化时,`dp[0][j] = 0`,因为没有...
基于动态规划的01背包问题,代码比较规范,注释比较详细。
用c语言实现的基于动态规划求解01背包问题,,其中2.txt中的内容为: 4 5 2 1 3 2 12 10 20 15
在本文中,我们将深入探讨一个具体的动态规划问题,即多重背包问题。多重背包问题与经典的0-1背包问题有所不同,它允许每种物品可以被选择多次,直至达到其最大数量限制。 题目描述了一个动态规划专题,其中涉及一...