0-1背包问题

题目

一个背包总容量为V，现在有N个物品，第i个物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？
(0-1背包问题指的是每个物品只能使用一次)

思路

定义一个二维数组dp[][]，大小为N×V
dp[i][j]：把前i个物品（从第1个到第j个）装入容量为j的背包中获得的最大价值
从dp[0][0]递推到dp[N][V]

现在递推dp[i][j]，分两种情况
1、第i个物品的体积比容量j大，装不进去 dp[i][]=dp[i-1][j]

2、第i个物品的体积比容量j小，能装进去(这时候再分两种情况：装或不装第i个物品)
不装第i个: dp[i][j]=dp[i-1][j]
装第i个: dp[i][j]=dp[i-1][j-weight[i]]+value[i]

代码

#include<bits/stdc++.h>
using namespace std;
const int N=10000;
int weight[N];
int value[N]; 
int dp[N][N];

int solve(int i,int j){
	if(dp[i][j]!=0){    //记忆化 
		return dp[i][j];
	}
	if(weight[i]>j){
		dp[i][j]=solve(i-1,j);
	}
	else{
		dp[i][j]=max(solve(i-1,j),solve(i-1,j-weight[i])+value[i]);
	}
	return dp[i][j];
	
}

int main(){
	int N,V;
	cin>>N>>V;
	for(int i=0;i<N;i++){
		cin>>weight[i]>>value[i];
	}
	memset(dp,0,sizeof(dp));
	cout<<solve(N,V)<<endl; 
	return 0;
}

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

文章来源: blog.csdn.net，作者：开心星人，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_55675216/article/details/123928319