【动态规划法】0-1背包问题

简介: 【动态规划法】0-1背包问题

  问题如下:

问题描述:

给定n个重量为wi,价值为vi的物品(i=1,2,…,n),以及一个重量为W的背包,找出其中最有价值的物品子集,并且能全部放入背包中。

输入样例:(第一行是背包重量上限,第二、三、四、五行是物品的重量和价值)

10

7 42

3 12

4 40

5 25

输出样例:(能够放入背包的物品最大价值)

65

代码如下:

#include <iostream>
#include <algorithm>//max()函数头文件 
#include <cstring>//memset函数头文件 
using namespace std;
#define N 100
int main(){
  int dp[N][N];
  memset(dp,0,sizeof(dp)); 
  int n=4;//共四件物品 
  int BagMax;cin>>BagMax;//输入背包最大容量 
  int height[N];int value[N];//物品重量数组,物品价值数组 
  int MaxValue=0;
  for(int i=1;i<=n;i++){//应该从1开始,下方初始化操作dp[i][j]=dp[i-1][j];  i需要>=1 
    cin>>height[i]>>value[i];//输入物品的重量、价值 
  } 
  for(int i=1;i<=n;i++){//仅对i个物品选择  
    for(int j=0;j<=BagMax;j++){//穷尽背包空间 
      dp[i][j]=dp[i-1][j];//初始化
      if(height[i]<=j){//第i个物品重量在背包可容纳范围内 
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-height[i]]+value[i]);
        if(dp[i][j]>MaxValue){MaxValue=dp[i][j];} 
      } 
    }
  } 
  cout<<MaxValue<<endl;
  return 0;
}

image.gif


目录
打赏
0
0
0
0
2
分享
相关文章
|
8月前
|
C++
每日练习之——背包问题
每日练习之——背包问题
39 1
动态规划:分组背包问题
动态规划:分组背包问题
98 0
动态规划法
动态规划是在20世纪50年代由美国数学家贝尔曼为研究最优控制问题而提出的,当该方法在应用数学中的价值被大家认同以后,在计算机学界,动态规划法成为一种通用的算法设计技术用来求解多阶段决策最优化问题。
【33. 0 1 背包问题】
背包问题 - 一共有N件物品,背包容量为V,物品有俩个属性,一个是体积一个是价值(类似在一个宝岛上,你有一个背包,它只能装满这个背包,小岛上有很多金子,各种体积的,而且每个金子纯度不一样,看最后怎么装才会使得背包中的金子价值最高) **四种背包问题** - 0 1 背包 每件物品最多只用一次, - 完全背包 每件物品有无线个 - 多重背包 每个物品不一样,每个物品最多有有S<sub>i</sub>个——朴素版和优化版 - 分组背包 有水果,汽车,人等,每一种里面最多只能选择一个
170 0
【33. 0 1 背包问题】
背包问题(二)
复习acwing算法基础课的内容,本篇为讲解基础算法:动态规划——背包问题,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
102 0
背包问题(二)
背包问题(一)
复习acwing算法基础课的内容,本篇为讲解基础算法:动态规划——背包问题,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
132 0
背包问题(一)
背包问题系列之 0-1 背包问题
背包问题系列之 0-1 背包问题
221 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等