【题目描述】

设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。

【输入描述】

第一行：两个整数，MM(背包容量，M≤200)和NN(物品数量，N≤30N≤30)；

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

【输出描述】

仅一行，一个数，表示最大总价值。

【样例输入】

10 4 
2 1 
3 3
4 5 
7 9

【样例输出】

12

【题目分析】

1. 状态定义

集合：放入背包的物品方案

限制：选择物品的范围，背包大小

属性：价值

条件：最大

统计量：价值

状态定义：dp[i][j]：在前i个物品中选择物品放入大小为j的背包能获得的最大价值。

初始状态：前0个物品放入大小为j的背包，价值为0。所以dp[0][j] = 0。

2. 状态转移方程

集合：在前i个物品中选择物品放入大小为j的背包的所有方案。

分割集合：是否选择第i物品放入背包

子集1：如果不选择第i物品，那么前i个物品中选择物品放入大小为j的背包，就是在前i-1个物品中选择物品放入大小为j的背包。能获得的最大价值为dp[i][j] = dp[i-1][j]。

子集2：如果选择第i物品，相当于先选了一个第i物品，价值是c[i]。接下来还需要在前i个物品中选择物品放入大小为j-w[i]的背包

。能获得的最大价值为dp[i][j] = dp[i][j-w[i]] + c[i]

以上两种情况求最大值

【参考答案】：二维数组

#include<bits/stdc++.h>
using namespace std;
#define N 35
#define M 205
int m, n, dp[N][M], w[N], c[N];//dp[i][j]：在前i个物品中选择物品放入大小为j的背包能获得的最大价值
int main()
{
    cin >> m >> n;//m：背包容量 n：物品数 
    for(int i = 1; i <= n; ++i)
        cin >> w[i] >> c[i];//w[i]：第i物品的重量 c[i]：第i物品的价值 
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= m; ++j)
        {
            if(j >= w[i])
                dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+c[i]);
            else
                dp[i][j] = dp[i-1][j];
        }
    cout << "max=" << dp[n][m];
    return 0;
}

【参考答案】：一维数组

#include<bits/stdc++.h>
using namespace std;
#define N 35
#define M 205
int m, n, dp[M], w[N], c[N];//dp[i][j]：在前i个物品中选择物品放入大小为j的背包能获得的最大价值
int main()
{
    cin >> m >> n;//m：背包容量 n：物品数 
    for(int i = 1; i <= n; ++i)
        cin >> w[i] >> c[i];//w[i]：第i物品的重量 c[i]：第i物品的价值 
    for(int i = 1; i <= n; ++i)
        for(int j = w[i]; j <= m; ++j)
            dp[j] = max(dp[j], dp[j-w[i]]+c[i]);
    cout << "max=" << dp[m];
    return 0;
}