企业营销型网站建设开发,衡阳网页设计,软件程序员,营销推广方案怎么写有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi#xff0c;价值是 wi。 求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。 输出 最优选法的方案数。注意答案可能很大#xff0c;请输出答… 有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi价值是 wi。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出 最优选法的方案数。注意答案可能很大请输出答案模 10971097 的结果。 输入格式: 第一行两个整数NV用空格隔开分别表示物品数量和背包容积。 接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 i件物品的体积和价值。 输出格式: 输出一个整数表示 方案数 模 10971097 的结果。 数据范围: 0N,V≤1000 0vi,wi≤1000 输入样例 4 5 1 2 2 4 3 4 4 6 输出样例 2 解题思路 题目是基于01背包的基础上进行扩展。核心还是01背包思路01背包的核心就是由初始条件递推下一个状态的最优解并记录。再由记录的最优解递推下一个状态的最优解层层递进。而本题是求最优选法方案数实质上也是一样由初始条件递推并记录最优解并层层递进。
值得注意的是本题求最优选法的方案数。所以选不选这个方案和这个方案所对应背包装入价值有关即选择装入最大价值的方案。【注意两种方案即不装第i件物品与装入第i件物品价值相等说明两种方案都可以要相加。】
此外如果数据比较大且大于等于10^9 7的话可以 mod 10^9 7。
如果还是觉得有些许疑虑还是强烈建议用输入样例将01背包的运行原理手动运行一下深究其规律可能会有质的飞跃。
理论成立代码如下朴素法容易理解
import java.util.*;public class Main {public static int N 1010;public static int mod (int)(1e9 7);public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int m sc.nextInt();int v[] new int[N];int w[] new int[N];for(int i 1;i n; i ) {v[i] sc.nextInt();w[i] sc.nextInt();}int count[][] new int[n 10][m 10];//记录方案数int f[][] new int[n 10][m 10];for(int i 0; i m; i ) count[0][i] 1;//什么也不装也是一种装法。count[i][0]会被自动迭代成1不必担心for(int i 1; i n; i )for(int j 0; j m; j ) {if(j v[i]) {count[i][j] count[i - 1][j];//装不了和前i-1的装法一样f[i][j] f[i - 1][j];}else {if(f[i - 1][j - v[i]] w[i] f[i - 1][j])count[i][j] count[i - 1][j - v[i]];else if(f[i - 1][j - v[i]] w[i] f[i - 1][j])count[i][j] count[i - 1][j - v[i]] count[i - 1][j];//两种方案都最优秀最佳方案数要相加elsecount[i][j] count[i - 1][j];//不相等选价值最大的f[i][j] Math.max(f[i - 1][j], f[i - 1][j - v[i]] w[i]);}if(count[i][j] mod)count[i][j] count[i][j] % mod;}System.out.print(count[n][m]);}
}
