解题思路:该问题明显就是动态规划,限定的使用资源(N元预算),每件商品选择买或者不买(0/1选择),给出商品数量;只需要使用动态规划经典思路,dp二位列表,dp[i][j]=dp[i-1][j](忽略该商品不买),dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+v[i]*level[i])(可购买此商品,选择最大价值与等级积),注意v[i]*level[i]的这个地方应根据具体题目要求改变,这里是最大价值与等级积
注意事项:注意尽量用1开始的下标,不然容易搞混
参考代码:
a,b=map(int,input().split())
dp=[[0]*(a+1) for _ in range(b+1)]
for i in range(1,b+1):
value,level=map(int,input().split())
for j in range(1,a+1):
if j>=value:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-value]+value*level)
else:
dp[i][j]=dp[i-1][j]
print(dp[b][a])
0.0分
1 人评分
小九九 (C语言代码)浏览:825 |
C语言训练-排序问题<1> (C++代码)浏览:603 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:904 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:526 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:575 |
数组输出 (C语言代码)浏览:703 |
简单的a+b (C语言代码)浏览:504 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:840 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:546 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:722 |