算法Day23 简单吃饭(0-1背包)
2023-12-13 22:02:02
简单吃饭(0-1背包)
Description
Input
Output
Sample
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int total = scanner.nextInt();
int price[] = new int[n];
int high[] = new int[n];
for(int i =0;i<n;i++){
price[i] = scanner.nextInt();
high[i] = scanner.nextInt();
}
System.out.println(process(price,high,total));
}
public static int process(int price[],int high[],int prices){
//总计happy
int dp[][] = new int[price.length+1][prices+1];
for(int i=1;i<=price.length;i++){
for(int j=1;j<=prices;j++){
dp[i][j]=dp[i-1][j];
if(j>=price[i-1]){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-price[i-1]]+high[i-1]);
}
}
}
return dp[price.length][prices];
}
}
思路
使用动态规划,与完全吃饭类似
注意的是dp[i][j]=dp[i-1][j]
这样是保证选取的食物有序,对食物仅能选取0-1次
文章来源:https://blog.csdn.net/m0_60695518/article/details/134867602
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!