题解：P1060 [NOIP2006 普及组] 开心的金明

sjh0626 · 2025-01-16 09:05:35 · 题解

思路分析

这道题我们可以用背包来做（其实就是动态规划），首先他说总和是 v_{j1} \times w_{j1} + v_{j2} \times w_{j2} + \dots + v_{jk} \times w_{jk}。

所以价格 v_i 就要转换为 v_i \times w_i。

然后我们有两种方法去讨论第 i 种物品（即 dp[i][j]）：

• 不取这件物品，就是只有前 i-1 个物品的价值，转化为 dp[i-1][j]。

• 取这件物品，就会只有前 i-1 个物品的价值，再去掉这个物品的容量，在后面再加上这个物品的价值，转化为

对于每种物品，我们取这个物品每种情况的最大值就行了。

即动态转移方程 dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])。

最后我们用滚动数组来优化它就可以了，因为我们只需要 i-1 行的数据，至于上面 i-2,i-3,\dots,1 行的数据都不需要了。

代码解析

#include<bits/stdc++.h>
#define sjh0626s return
#define code 0
using namespace std;
int v[10100],w[10100],n,m,dp[30100];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
        v[i]*=w[i];
    } 
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        } 
    }
    cout<<dp[m];
    sjh0626s code;
}