vivo2019提前批软开笔试第三题(0、1背包问题的动态规划求解)

朴灿烈づ我的快乐病毒、 2021-09-29 00:16 204阅读 0赞

# 一、题目 #

题目来源参考：[https://www.cnblogs.com/ChangAn223/p/10976940.html][https_www.cnblogs.com_ChangAn223_p_10976940.html]

题目描述：小v负责一次活动礼品采购，每一款礼品的受欢迎程度（热度值）各部相同，现给出总金额以及各礼品单价和热度，且每个礼品只能采购一个，如何购买可以使得所有礼品的总热度值最高。

输入：

1.  第一行是一个正整数，表示总金额（不大于1000）
2.  第二行是一个长度为n的正整数数组，表示礼品单价（n不大于100）（笔者注：感觉这个值给错了，应该是1000，因为给的输入示例值最大为600）
3.  第三行是一个长度为n的正整数数组，表示对应的礼品热度值。

输出：

1.  一个正整数，表示可获得的最高热度值。

（任选一种语言作答，多选语言不加分）

样例输入：

1000

200 600 100 180 300 450

6 10 3 4 5 8

样例输出：

注：以下是python对应题目的给出代码（因有部分被遮挡，仅供参考）

# -*- coding:utf-8 -*-
    import sys
    
    
    def solution(n, total_money, unit_price, hotspot_val):
        """
    
        :param n: 礼品总数量
        :param total_money: 总金额
        :param unit_price: 礼品单价
        :param hotspot_val: 礼品热度值
        :return:
        """
        # 置零，表示初始状态
        val = [[0 for j in range(total_money+1)] for i in range(n+1)]
    
        # TODO write your code here
        # 自写代码部分
    
        return val
    
    
    if __name__ == "__main__":
        try:
            total_money = int(raw_input("请输入总金额: "))  # 正整数；raw_input
            unit_price = raw_input("请输入各个商品的单价，单价间使用空格分隔: ").split()
            unit_price = [int(item) for item in unit_price]
            hotspot_val = raw_input("请输入各个商品的热度，使用空格分隔：").split()
            hotspot_val = [int(item) for item in hotspot_val]
        except Exception as err:
            print err
            print "输入有误"
            sys.exit()
        n = len(unit_price)
        value = solution(n, total_money, unit_price, hotspot_val)
    
        print value[n][total_money]

# 二、问题解决 #

python代码：

# -*- coding:utf-8 -*-
    import sys
    
    
    def solution(n, total_money, unit_price, hotspot_val):
        """
        返回最大热度
        :param n: 礼品总数量
        :param total_money: 总金额
        :param unit_price: 礼品单价
        :param hotspot_val: 礼品热度值
        :return:
        """
        # 置零，表示初始状态
        val = [[0 for j in range(total_money+1)] for i in range(n+1)]
    
        # TODO write your code here
        # 自写代码部分
        val[0] = [0 for j in range(total_money+1)]  # 礼品数量为0时，无论有多少钱都没用
        if n == 0:
            return val
        for I in range(1, n+1):
            "商品数确定为I的情况"
            val[I][0] = 0  # 总金额为0时，必为0
            for J in range(1, total_money+1):
                """ 钱数确定为J的子情况"""
                with_out_current = val[I-1][J]  # 不放当前的“新商品”可获得的最大热度
                if J >= unit_price[I-1]:
                    # 先放入当前商品，再加上剩余的钱在没有当前商品时可获得的最大热度
                    with_current = hotspot_val[I-1] + val[I-1][J-unit_price[I-1]]
                else:
                    with_current = with_out_current
                # 取with_current与with_out_current之间的较大者
                if with_current > with_out_current:
                    val[I][J] = with_current
                else:
                    val[I][J] = with_out_current
        return val
    
    
    if __name__ == "__main__":
        try:
            total_money = int(raw_input("请输入总金额: "))  # 正整数；raw_input
            unit_price = raw_input("请输入各个商品的单价，单价间使用空格分隔: ").split()
            unit_price = [int(item) for item in unit_price]
            hotspot_val = raw_input("请输入各个商品的热度，使用空格分隔：").split()
            hotspot_val = [int(item) for item in hotspot_val]
        except Exception as err:
            print err
            print "输入有误"
            sys.exit()
        n = len(unit_price)
        value = solution(n, total_money, unit_price, hotspot_val)
    
        print value[n][total_money]

解题思路，用“动态规划”的思想。模拟表格，横行第一行代表“总钱数递增”，竖行第1行代表对应的“商品对象价格”

模拟表格

[https_www.cnblogs.com_ChangAn223_p_10976940.html]: https://www.cnblogs.com/ChangAn223/p/10976940.html