倒计时四天：动态规划
学习动态规划的经典问题
一、背包问题：
有N件物品和一个容量为V的背包。第i件物品的价值是C[i]，重量是W[i]。求解将哪些物品装入背包可使价值总和最大。
输入描述:
输入第一行数 N V (1 <=N <=500) (1<= V <= 10000)
输入 N行 两个数字 代表 C W (1 <= C <= 50000, 1 <= W <=10000)
输出描述：
输出最大价值
输入
5 10
8 6
10 4
4 2
5 4
5 3
输出
19
代码：
#include<iostream>
#include<math.h>
using namespace std;
const int max_n=501,max_w=10001;
int num[max_n][max_w];
int n,v;
int w[max_n],c[max_n];
int main(){
cin>>n>>v;
for(int i=0;i<n;i++){
cin>>c[i]>>w[i];
}
for(int i=n-1;i>=0;i--){
for(int j=0;j<=v;j++){
if(j<w[i]){
num[i][j]=num[i+1][j];
}
else{
num[i][j]=max(num[i+1][j],num[i+1][j-w[i]]+c[i]);
}
}
}
printf("%d\n",num[0][v]);
} 
投递美团等公司10个岗位 >