背包问题求助

在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]。
基础解决方法是二维状态数组,然后有个优化空间的解决办法——用一维状态数组。

不懂的地方是为什么双重循环里第二个要倒序
网上看到两种解释:
1. 正序枚举A[i],并倒叙枚举j,这样所需要的dp[j-A[i]]不会被提前更新

2,因为新的结果要与其在二维素组中左上位置的元素比较(即一维数组中左边的元素比较),所以从后向前遍历一维数组

但是都看不太懂,有没有好心人愿意探讨一下#晒一晒我的offer##现在还是0offer,延毕还是备考##0offer是寒冬太冷还是我太菜#(引流)
全部评论
因为如果用一维背包且正序遍历,考虑把当前的物体放进背包时需要j-A【i】的状态,而这个状态如果是正序遍历就是已经被计算过了(即已经考虑要不要把当前物体放进背包了),这样就相当于一个物体可以被多次选择了,变成了完全背包问题。所以对于01背包一维dp需要倒序遍历
1 回复 分享
发布于 2023-09-26 23:30 江苏

相关推荐

import java.util.Scanner;public class demo {public static void main(String[] args) {//移除链表元素//构造链表1-->4-->2-->4Scanner sc = new Scanner(System.in);int n = sc.nextInt();//链表共有节点个数sc.nextLine();//构造单链表  尾插法ListNode head = null;//head一旦确定,就不再移动ListNode tail = null;//随着新节点的加入,不断向后移动if (n > 0){for (int i = 1; i <= n; i++){int val = sc.nextInt();//输入链表ListNode newNode = new ListNode(val);if (head == null){//插入第一个节点时,head既是头又是尾head = newNode;tail = head;}else{tail.next = newNode;tail = tail.next;}}}sc.nextLine();int target = sc.nextInt();//需要移除的目标值//如果头节点本身就要删除while (head != null && head.val == target){head = head.next;//直接将head后移}//判断是否为空if (head == null){return;}//处理头节点之后的节点ListNode current = head;while (current.next != null){if (current.next.val == target){//找到目标,则移除current.next = current.next.next;}else {//没找到,继续向后current = current.next;}}while (head != null){System.out.print(head.val + " ");head = head.next;}}}class ListNode{int val;ListNode next;ListNode(int val){this.val = val;}}
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务