【动态规划法】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
分享
相关文章
|
4月前
|
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
153 2
动态规划算法学习三:0-1背包问题
|
9月前
|
动态规划—(背包问题)
动态规划—(背包问题)
【动态规划】多重背包问题,分组背包问题
与完全背包问题不同的是,每种东西都是有限件,前两种状态就不再过多赘述
157 4
动态规划之背包问题
动态规划之背包问题
107 0
动态规划——多重背包、分组背包
动态规划——多重背包、分组背包
69 0
动态规划:多重背包问题
动态规划:多重背包问题
79 0
动态规划:分组背包问题
动态规划:分组背包问题
98 0
AI助理

你好,我是AI助理

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