LintCode刷题笔记-- BackpackIII
2024-09-06 14:02:42
标签:动态规划
问题描述:
Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?
解题思路:
又是一道恶意满满的背包问题,显然这道题我想复杂了,开始思路利用前一道题的true,false 标记的方法来解这一道题,在有恰好解的重量上进行标记,之后再对所有标记过的恰好解进行遍历找出最大的。中间还用到了面向对象的内容。显然,在方法上,这道题我想复杂了,在思路上还是没有搞清状态转移方程的真实含义。
对于这道背包问题:
1. 从两个向量分解问题的内容,一个是拥有的背包物品数量,另外一个是背包可以拥有的最大重量。
2. 对于每次增加一个物品,是否加入背包,需要与上一次(不加入该物品的情况下)背包总价值进行比较,如果价值更大就加入该物品,否则与上一次不加入该物品的总价值相同。
加入这样物品在某个重量下的临界值,才会与之前没加入这项物品的情况作出比较。
用子问题定义状态:即f[i][v]表示前 i 件物品恰放入一个容量为 j 的背包可以获得的最大价值。则其状态转移方程便是: f[i][j] = max{f[i-1][j], j>=A[i-1]? f[i-1][j-A[i-1]]+V[i-1] : 0}
参考代码:
public int backPackII(int m, int[] A, int V[]) {
// write your code here
int[][] dp = new int[A.length+1][m+1];
dp[0][0] = 0;
for(int i=1; i<=A.length; i++){
for(int j = 0; j<=m; j++){
if(j<A[i-1]){
dp[i][j]=dp[i-1][j];
}else if(j>=A[i-1]){
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-A[i-1]]+V[i-1]);
} }
}
return dp[A.length][m];
}
最新文章
- NotifyIcon 将窗口最小化到托盘
- Rhel6-lanmp架构配置文档
- POJ 1661 Help Jimmy (dijkstra,最短路)
- 13、SQL Server 自定义函数
- ural 1671 Anansi&#39;s Cobweb
- POJ1742:Coins(多重背包)
- Xamarin.Forms 初探
- Java基础总结--异常处理机制
- 裴波那契查找详解 - Python实现
- Linux之服务管理
- Java SE之[静态成员/类成员]与[非静态成员/实例成员]【static】
- 410 for 循环 运算 改变循环的控制流 死循环 遍历数组 定义方法 有名函数匿名函数 定义函数的方法取值 date math 局部变量 函数 局部与全局变量 次幂/随机数/取绝对值/向上取整/平方根
- 我了解到的新知识之—Apple Captive Portal 网页认证登陆公共Wifi
- eShopOnContainers 看微服务 ②:配置 启动
- Android Studio向项目中导入jar包的方法
- libSVM在matlab下的使用安装
- 【jQuery Demo】图片瀑布流实现
- tensorflow初始化函数变更
- Redis实战总结-配置、持久化、复制
- git如何回滚当前修改的内容?