洛谷p1498c语言

### 洛谷 P1498 题目解析

对于洛谷P1498题目，该问题属于动态规划中的完全背包变种问题。此题的核心在于理解如何通过给定的数据构建状态转移方程并实现最优解。

#### 动态规划思路
为了处理这个问题，定义`dp[i][j]`表示前i个物品恰好放入容量为j的背包的最大价值。初始化时设置`dp[0][0]=0`，其余位置设为负无穷大以确保初始状态下无法达到的状态不会影响后续计算[^1]。

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 105;
int dp[MAXN][MAXN];
int weight[MAXN], value[MAXN];

void solve() {
    memset(dp, -63, sizeof(dp));
    dp[0][0] = 0;
    
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        cin >> weight[i] >> value[i];
        for (int j = 0; j <= V; ++j) {
            if (j >= weight[i])
                dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]] + value[i]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }

    cout << *max_element(dp[n], dp[n]+V+1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    solve();
}

上述代码实现了二维数组形式的记忆化搜索版本，其中包含了读取输入数据、更新状态以及最终输出结果的过程。这里采用了一维滚动数组优化空间复杂度至O(V)，使得程序更加高效。