早教吧作业答案频道 -->其他-->
用动态规划做,不用深度优先搜索,伪代码或思路即可,背包问题(snap.pas)设有一个背包,可以放入的重量为s.现有n件物品,重量分别是W1,W2,...,Wn,均为正整数,从n件物品中挑选若干件,使得放入背
题目详情
用动态规划做,不用深度优先搜索,伪代码或思路即可,
背包问题(snap.pas)
设有一个背包,可以放入的重量为s.现有n件物品,重量分别是W1,W2,...,Wn,均为正整数,从n件物品中挑选若干件,使得放入背包的重量正好是s.找到一组解即可.
输入格式:第一行是物品的总件数和背包的载重量,第二行是各物品的重量.
输出格式:各所选物品的序号和重量.
【样例】
Snap.in 5 10
1 2 3 4 5
Snap.out
Numbet:1 weight:1
Numbet:4 weight:4
Numbet:5 weight:5
伪代码就可以了,
背包问题(snap.pas)
设有一个背包,可以放入的重量为s.现有n件物品,重量分别是W1,W2,...,Wn,均为正整数,从n件物品中挑选若干件,使得放入背包的重量正好是s.找到一组解即可.
输入格式:第一行是物品的总件数和背包的载重量,第二行是各物品的重量.
输出格式:各所选物品的序号和重量.
【样例】
Snap.in 5 10
1 2 3 4 5
Snap.out
Numbet:1 weight:1
Numbet:4 weight:4
Numbet:5 weight:5
伪代码就可以了,
▼优质解答
答案和解析
开一个bool数组f,f[i][j]表示是否可以用前i件物品【刚好】占用j的容量,初始化f[0..n][1..s]=false,f[0][0]=true.然后:for i=1 to n for j=w[i] to s f[i][j]=f[i-1][j] or f[i-1][j-w[i]];最后输出结果只...
看了用动态规划做,不用深度优先搜索...的网友还看了以下:
数轴上表示整数的点称为整点.某数轴的单位长度是1cm,若在这个数轴上随意画出一条长为4cm的线段A 2020-05-13 …
数轴上的点称为整点,某数轴的单位长度是1厘米,若这个数轴上随意画出一条长2010厘米的线段AB,它 2020-05-16 …
数轴上表示整数的点称为整点,某数轴的单位长度为1cm,若在这个数轴上随意划出一条长2010cm的线 2020-06-05 …
数轴上表示整数的点称为整点,某数轴的单位长度为1cm,若在这个数轴上随意划出一条长2010cm的线 2020-06-06 …
三边长都是整数的三角形称为整边三角形,请问周长为6的整边三角形有多少个设每根火柴为1,请动手摆一摆 2020-06-10 …
数轴上表示整数的点称为整点,某数轴的单位长度为1cm,若在数轴上画出一条长2004cm的线段AB则 2020-06-20 …
【数论:奇数与偶数】设a,b,c为整数,证明:(a+b+c)(a+b-c)(b+c-a)(c+a- 2020-06-27 …
求这样的打折公式?内有要求?1.打折的结果:2902.要求5折以上的折扣3.要求折扣率为整数或者为两 2020-11-08 …
如何用SQL语句全局搜例如:我有表AAA如下,列名为abc,列内容如下:abcaabbccddaad 2020-12-21 …
调整下列语句的顺序,使之成为一段语意连贯的话。将调整后的序号写在下面的横线上。A.特别重要的,是要有 2021-01-13 …