题解 | #点菜问题#优化成一维

点菜问题

https://www.nowcoder.com/practice/b44f5be34a9143aa84c478d79401e22a

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

int weight[2000];
int value[2000];
int dp[2000]; //dp[j]容量还有j, 当前价值为dp[j]


int main() {
    int n, m; //n件物品, m为总容量
    while (scanf("%d%d", &m, &n) != EOF) {
        for (int i = 1; i <= n; i++) { //从1开始
            scanf("%d%d", &weight[i], &value[i]);
        }
        for (int i = 0; i <= m;
                i++) { //当啥都不选的时候,就算有再多的容量也没用
            dp[i] = 0;
        }
        for (int i = 1; i <= n; i++) { 
            for (int j = m; j >= weight[i]; j--) {
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        printf("%d\n", dp[m]);
    }
}

全部评论

相关推荐

牛客771574427号:恭喜你,华杰
点赞 评论 收藏
分享
11-18 15:57
门头沟学院 Java
最终归宿是测开:这个重邮的大佬在重邮很有名的,他就喜欢打92的脸,越有人质疑他,他越觉得爽😂
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务