实验报告 动态规划 01背包 问题_动态规划01背包问题实验报告

一.题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤10000 0<vi,wi≤10000

 二.思路分析

关键 确定数组 dp的含义 dp[i] [j] 表示的是当剩余背包容量为j时，对于前i个物体，背包所能拥有的最大价值。

那么我们首先分析动态规划的边界，也就是我们分析数组 dp它获得确定值的过程，很显然应该按从小到大的顺序，可以避免数据的溢出，

那么 我们通过分析可以直接得到，状态转移方程:

for(int i=1;i<=n;i++)
	{
 		for(int j=1;j<=capacity;j++)
		{
			if(j<weight[i-1])
			{
				dp[i][j]=dp[i-1][j];
			}
			if(j>=weight[i-1])
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);
			}
		}
	}

这里我来解释一下，

首先假如背包里面剩余的空间也就是 j 小于物品的空间，很显然是放不进去的，那么对于dp[i][j],这i个物体所能产生的最大价值，很显然和把这个物体去掉，前面i-个物体所产生的价值dp[i-1][j]是相等的，

那么讨论另一种情况

加入背包里面剩余的空间 j 大于第i个物体的空间，很显然此时能够放进去，所以 dp[i][j]的值会产生改变， 分两种情况，这里是最复杂的敌方，我先给出代码 ，再根据代码解释；

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);

首先为什么会有两种情况，很容易出现的一个疑问是 为什么要和dp[i-1][j] 比大小，加进去东西后不是肯定会比原来的情况沉吗？

是的，但是只是暂时的价值增加了，而原本应该放进去的东西却因为空间不够，放不进去，形象的来说，就是丢了西瓜，捡了芝麻·，所以我们才进行了比较，注意我们用于比较的是dp[i-1][j-weight[i-1]]+value[i-1]，可以发现如果增加了value[i-1]，并不是在原有的基础上直接加的，我们的容量也会相应变小，变为了   j-weight  ，而我们调用之前动态规划计算出来的值，进行比较，

总的说，感觉可以理解成 我们虽然把这个物体暂时装了进去 ，但是我们未来装的物体就少了，

就是把数组dp的含义完全理解就ok了

当然我们也可以跟据动态规划的定义每一步按照步骤严格进行。

三.源代码

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int capacity;
	cin>>capacity;
	int value[n];
	int weight[n];
	int dp[n+1][capacity+1];//共有n件物品
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++)
	{
		cin>>value[i]>>weight[i];
	}
 
	for(int i=1;i<=n;i++)
	{
 		for(int j=1;j<=capacity;j++)
		{
			if(j<weight[i-1])
			{
				dp[i][j]=dp[i-1][j];
			}
			if(j>=weight[i-1])
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);
			}
		}
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=capacity;j++)
		{
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}	
	
	return 0;
}

四.测试数据及结果

4
8
3 2
4 3
5 4
6 5

0 0 0 0 0 0 0 0 0
0 0 3 3 3 3 3 3 3
0 0 3 4 4 7 7 7 7
0 0 3 4 5 7 8 9 9
0 0 3 4 5 7 8 9 10

五.遇到的问题及解决方法

首先还是对于动态规划的步骤更加熟悉了嘛

另外还有一点关于二维数组的基础知识不太懂、

对于二维数组的全部变量进行赋值的话

为什么

int dp[n+1][capacity+1]={0};

这种方法不行？？

还学了一种新方法

来自c语言的一个函数

首先是头文件

#include<cstring>

函数如下

memset(dp,0,sizeof(dp));

但是好像赋值的范围只能是0和-1；

over!