题解

题目难度：中等

知识点：字符、动态规划、数组、递归、记忆化搜索

方法（一）动态规划

解析问题：本题可以分析为典型的01背包问题，使用动态规划就可以解决问题。在分析问题时，主要解析为以下三步。
第一步：确定【状态】和【选择】。
在本题中，【状态】就是“剩余的空间大小总和”和“可选择的资产”，【选择】就是“放入这个资产”和“不放入这个资产”。
第二步：要明确 dp 数组的定义。
第三步：根据【选择】，对状态转换的逻辑进行计算。

思路

第二步定义数组意义：在这里，使用二维的思维创建dp的形式。设置 dp[i][j] ，i表示可选择的资产类型数，j表示剩余的可选资产zong'shu
第三步分析逻辑：如果不把 weight[i] 算入子集，那么是否能够恰好等于总和，取决于上一个状态 dp[i-1][j]。如果把 weight[i] 算入子集，那么是否能够恰好等于总和，取决于状态 dp[i - 1][j-weight[i-1]]。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int SumVal,type;
    //通过char的方式将逗号分出来，分隔出数字进行保存
    char c;
    cin >> SumVal >> c >> type >> c;
    //定义MaxVal[][]
    vector<vector<int> > MaxVal(type+1,vector<int>(SumVal+1,0));
    int weight[type];
    int val[type];
    for(int i=0;i<type;i++)
    {
        int a;
        cin>>a;
        weight[i]=a;
    }
    cin>>c;
    for(int i=0;i<type;i++)
    {
        int a;
        cin>>a;
        val[i]=a;
    }
    for(int i=1;i<=type;i++)
        for(int j=1;j<=SumVal;j++)
        {
            if(j>=weight[i-1])
            {
                MaxVal[i][j]=max(MaxVal[i-1][j],MaxVal[i-1][j-weight[i-1]]+val[i-1]);
            }
            else
                MaxVal[i][j]=MaxVal[i-1][j];
        }
    cout<<MaxVal[type][SumVal];
    return 0;
}

方法（二）递归方法

【注】效率相当低下，只能通过26%的测试用例。

我们用F(n,C)表示将前n个物品放进容量为C的背包里，得到的最大的价值。我们用自顶向下的角度来看，假如我们已经进行到了最后一步（即求解将n个物品放到背包里获得的最大价值），此时我们便有两种选择：

选择一：不放第n个物品，此时总价值为F(n−1,C)

选择二：放置第n个物品，此时总价值为vn+F(n−1,C−wn)

因此，两种选择中总价值最大的方案就是我们的最终方案，其状态转移方程为：
F(i,C)=max(F(i−1,C),v(i)+F(i−1,C−w(i)))

#include<iostream>
using namespace std;
  /**
     * 解决背包问题的递归函数
     *
     * @param w        物品的重量数组
     * @param v        物品的价值数组
     * @param index    当前待选择的物品索引
     * @param capacity 当前背包有效容量
     * @return 最大价值
     */
    int solveKS(int w[], int v[], int index, int capacity) {
        //基准条件：如果索引无效或者容量不足，直接返回当前价值0
        if (index < 0 || capacity <= 0)
            return 0;
        //不放第index个物品所得价值
        int res = solveKS(w, v, index - 1, capacity);
        //放第index个物品所得价值（前提是：第index个物品可以放得下）
        if (w[index] <= capacity) {
            res = max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
        }
        return res;
    }

int main(){
    int c, n, i, j;
    char m;
    cin >> c >> m >> n >> m;
    int w[n], v[n];
    for(i = 0; i < n; i++) 
        cin >> w[i];
    cin >> m;
    for(i = 0; i <n; i++) 
        cin >> v[i];
    cout<<solveKS(w, v, n - 1, c);
    return 0;
}

方法(三)记忆化搜索

【注】方法二的改进
我们用递归方法可以很简单的实现以上代码，但是有个严重的问题就是，直接采用自顶向下的递归算***导致要不止一次的解决公共子问题，因此效率是相当低下的。
我们可以将已经求得的子问题的结果保存下来，这样对子问题只会求解一次，这便是记忆化搜索。

#include<iostream>
#define Maxn 1010
using namespace std;
int memo[Maxn][Maxn];
    /**
     * 解决背包问题的递归函数
     *
     * @param w        物品的重量数组
     * @param v        物品的价值数组
     * @param index    当前待选择的物品索引
     * @param capacity 当前背包有效容量
     * @return 最大价值
     */
    int solveKS(int w[], int v[], int index, int capacity){
        //基准条件：如果索引无效或者容量不足，直接返回当前价值0
        if (index < 0 || capacity <= 0)
            return 0;

        //如果此子问题已经求解过，则直接返回上次求解的结果
        if (memo[index][capacity] != 0) {
            return memo[index][capacity];
        }

        //不放第index个物品所得价值
        int res = solveKS(w, v, index - 1, capacity);
        //放第index个物品所得价值（前提是：第index个物品可以放得下）
        if (w[index] <= capacity) {
            res = max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
        }
        //添加子问题的解，便于下次直接使用
        memo[index][capacity] = res;
        return res;
    }

int main(){
    int c, n, i, j;
    char m;
    cin >> c >> m >> n >> m;
    int w[n], v[n];
    for(i = 0; i < n; i++) 
        cin >> w[i];
    cin >> m;
    for(i = 0; i <n; i++) 
        cin >> v[i];
    cout<<solveKS(w, v, n - 1, c);
    return 0;
}