signed

QiShunwang

“诚信为本、客户至上”

一维dp实现0-1背包问题

2021/3/21 0:53:51   来源:

dp(动态规划)实现0-1背包问题

1.什么是0-1背包问题?
0-1背包问题就是给定n种物品和一背包。物品 i 的重量为wi,其价值为 vi,背包的容量为 W。问应该如何选择装入背包中的物品,使得装入背包中物品的总价值最大

2.什么是dp
动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决

3.解决0-1背包的过程
问题转化为:满足约束条件的任一集合(x1,x2…,xn)是问题的一个可行解,问题是求到最优的解(x=0||x=1(0代表不含这个物品,1代表含该物品))
(1)刻画0-1背包的最优解的结构
把背包问题看作是一系列的策略,决定哪些物品要放入背包,哪些东西不要放入背包。如果某个问题的最优解包含了一个物品n,即xn=1,那么其他的x1,x2…xn-1构成了子问题1,2,3…n-1在容量为W-wn的最优解。反之xn=0,那么其他的x1,x2…xn-1构成了1,2,3…n-1在容量为W的最优解
(2)递归求解
(3)求出最优解的值
(4)求出最优解

4.代码实现(c代码)

一维dp

#include <iostream>
#include <algorithm>
#include <cstring>
#include<vector>
using namespace std;
 int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    vector <int> v(n+1),w(n+1),dp(m+1);
    for(int i=1;i<=n;i++)
    {
    	scanf("%d%d",&v[i],&w[i]);
	}
	for(int i = 0; i<=m+1; i++) 
 	{
  		dp.push_back(0);
 	}
	for(int i=0;i<=n;i++){
		for(int j=m;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	printf("%d\n",dp[m]);
}

样例:输入:
5 17
4 3
5 4
10 7
11 8
13 9
输出:
24