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

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