问题简述

【题目描述】：

一个旅行者有一个最多能装M公斤的背包，现在有n件物品，他们的重量分别是W1，W2…Wn，

它们的价值分别是C1，C2……Cn，求旅行者能够获得的最大总价值。

【输入格式】：

第一行：两个整数，M，（背包容量，M<=200）和N（物品数量N<=30）

第2至N+1行，每行两个整数，Wi,Ci,表示每个物品的重量和价值。

【输出格式】：仅一行，一个数，表示最大总价值。

【输入样例#1】：

10 4

2 1

3 3

4 5

7 9

【输出样例#1】：12

 

构建表格

行为物品的数量 列为背包容量

代码如下

#include
     
      using namespace std;#define max(x,y) x>y?x:yint bg[100][100]={
   0};int main(){    int m,n;    cin>>m>>n;    for(int i=1;i<=n;i++){        int w,c;        cin>>w>>c;        for(int j=1;j<=m;j++){            if(w<=j)                bg[i][j]=max(bg[i-1][j],bg[i-1][j-w]+c);            else                bg[i][j]=bg[i-1][j];        }    }    cout<