/*************************************************************************
* Compilation: javac Knapsack.java
* Execution: java Knapsack N W
*
* Generates an instance of the 0/1 knapsack problem with N items
* and maximum weight W and solves it in time and space proportional
* to N * W using dynamic programming.
*
* For testing, the inputs are generated at random with weights between 0
* and W, and profits between 0 and 1000.
*
* % java Knapsack 6 2000
* item profit weight take
* 1 874 580 true
* 2 620 1616 false
* 3 345 1906 false
* 4 369 1942 false
* 5 360 50 true
* 6 470 294 true
*
*************************************************************************/
public class Knapsack {
private int[] profit;
private int[] weight;
private int N;
private int W;
public Knapsack(int n, int w)
{
N = n;
W = w;
dataGeneration();
}
private void dataGeneration()
{
profit = new int[N + 1];
weight = new int[N + 1];
// generate random instance, items 1..n
for (int n = 1; n <= N; n++) {
profit[n] = (int) (Math.random() * 1000);
weight[n] = (int) (Math.random() * W);
}
}
public boolean[][] doKnapsack()
{
// opt[n][w] = max profit of packing items 1..n with weight limit w
// sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n?
int[][] opt = new int[N + 1][W + 1];
boolean[][] sol = new boolean[N + 1][W + 1];
for (int n = 1; n <= N; n++) {
for (int w = 1; w <= W; w++)
if (weight[n] <= w && (profit[n] + opt[n - 1][w - weight[n]] > opt[n - 1][w]))
{
opt[n][w] = profit[n] + opt[n - 1][w - weight[n]];
sol[n][w] = true;
}
else
{
opt[n][w] = opt[n - 1][w];
sol[n][w] = false;
}
}
return sol;
}
public void print(boolean[][] sol)
{
// determine which items to take
boolean[] take = new boolean[N + 1];
for (int n = N, w = W; n > 0; n--) {
if (sol[n][w]) { take[n] = true; w = w - weight[n]; }
else { take[n] = false; }
}
// print results
System.out.println("item" + "\t" + "profit" + "\t" + "weight" + "\t" + "take");
for (int n = 1; n <= N; n++) {
System.out.println(n + "\t" + profit[n] + "\t" + weight[n] + "\t" + take[n]);
}
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]); // number of items
int w = Integer.parseInt(args[1]); // maximum weight of knapsack
Knapsack app = new Knapsack(n, w);
boolean[][] sol = app.doKnapsack();
app.print(sol);
}
}
分享到:
相关推荐
本资源包含了0-1背包问题的最佳所有解法,其中包括动态规划算法,回溯法算法,分支限界算法和贪心算法。包含源代码。
如题,动态规划法求解0-1背包问题实验报告 大二算法作业 使用java语言实现 内容框架:问题描述 思路分析 实例分析 实验原码及运行结果 实验心得
算法实验中用动态规划法解0-1背包问题,这里提供了源代码,仅供参考
计算机算法设计与分析动态规划法求解0-1背包问题的改进算法完整解释
哈工程本科算法实验-0-1背包(动态规划-分支限界-回溯法)【数据+代码+说明+流程图+测试用例】
C++ 动态规划算法实现0-1背包问题 包含了代码、算法分析、测试文件和结果,非常详尽,值得拥有!
1) 动态规划法求解问题的一般思路,动态规划法求解本问题的思路及其C/C++程序实现与算法的效率分析。 2) 贪心算法在0-1背包问题求解中的应用 3) 回溯法求解问题的一般思路,回溯法求解本问题的思路及其C/C++程序实现...
基于MATLAB平台,用动态规划法解决0-1背包问题,较为简单。参数分别为[物品重量,物品价值,背包容量,背包价值]
"0-1"背包问题的贪心算法 "0-1"背包问题的动态规划算法 "0-1"背包问题的回溯算法
C语言是一门面向过程、抽象化的通用程序设计语言,广泛应用于底层开发。C语言能以简易的方式编译、处理低级存储器。C语言是仅产生少量的机器语言以及不需要任何运行环境支持便
0-1背包问题 动态规划 分支限界 回溯 贪心四种方法
-1背包问题是一个典型的算法问题,它有多种方法求解,请使用贪心法,动态规划和分支限界法编程求解
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
实验二 用动态规划法求解0/1背包问题 实验三 用贪心算法求解Prim算法 实验四 用回溯法求解N后问题 实验五 用分支限界法实现旅行售货员问题 这些实验的大部分源代码都是书上的, 我用的是WindowsXP SP2 VisualC++6.0...
数据结构 算法设计与分析背包问题的动态规划法算法
算法设计实验报告,包括:蛮力、动态规划、回溯、分支限界四种算法求解0/1背包问题的基本思想、时间复杂度分析,C++实现代码,运行结果截图,实验心得。
0/1背包问题是学习动态规划算法最经典的例子 Java代码实现0/1背包问题 代码里有详细的注释,比较好理解
算法大作业,0-1背包问题求解六种方法综述,包含动态规划算法,分支限界法,回朔法,蛮力法,贪心法,遗传算法的六种算法,有实验报告,运行结果截图,源码哦,有需要的小伙伴,自行下载哦
基于python实现贪心算法、蛮力法、动态规划法解决分数背包问题和0-1背包问题源码+项目说明及注释.zip 问题要求在一个物品集合中选择合适的物品放入背包,在放入背包中的物品总重量不超过背包容量的前提下,希望放入...