【晴问算法】提高篇—动态规划专题—01背包问题

题目描述

有n件物品，每件物品的重量为wi，价值为ci。现在需要选出若干件物品放入一个容量为V的背包中(每件物品至多选一次)，使得在选入背包的物品重量之和不超过容量V的前提下，让背包中物品的价值之和最大，求最大价值。

输入描述

第一行两个整数n、V(1<n<100,1≤V<10^3)，分别表示物品数量、背包容量,
第二行为用空格隔开的n个整数wi(1<wi<10)，表示物品重量;
第三行为用空格隔开的n个整数ci(1≤ci<10)，表示物品价值。

输出描述

输出一个整数，表示最大价值。

样例1

输入

5 8 3 5 1 2 2 4 5 2 1 3

输出

10

解释

假设物品编号为从1到5，那么选择第1、3、4、5 件物品时，物品重量值和为3+1+2+2=8，此时的价值是4+2+1+3 =10，是最大价值。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100;
int dp[MAXN][MAXN];//dp[i][j]表示[0:i]的物品放进容量j的背包里
int w[MAXN];//物品的重量
int c[MAXN];//物品的价值

int main(){
	int n,maxW;//n个背包最大容量是maxW
	cin >> n >> maxW;
	for(int i=0;i<n;i++){
		cin >> w[i];
	}
	for(int i=0;i<n;i++){
		cin >> c[i];
	}
	memset(dp,0,sizeof(dp));//所有初始为0
	for(int i=0;i<n;i++){//外循环先遍历物品
		for(int j=0;j<=maxW;j++){//内循环遍历背包
			if(i == 0){//i=0,j=0时dp=0，j不等于0时，要判断当前背包容量是否能装进第一个物品
				dp[i][j] = ((w[i] <= j) ? c[i] : 0);
			}else{//i不等于0，j=0则dp一定为0，其他数值要判断当前背包容量能否容纳前i个物品
				dp[i][j] = max((w[i] <= j) ? dp[i-1][j-w[i]]+c[i] : 0,dp[i-1][j]);	
			}
		}
	}
	printf("%d",dp[n-1][maxW]);//前n-1个（0~n）物品装入maxW的背包里
	return 0;
}