01背包问题的取和不取实际上就是一个机会成本的问题,如果取了某件东西,尽管当前的价值暂时地增加了,但你付出了机会成本。因为如果不取,留下的空间以后说不定可以放更有价值的东西。因此空间和价值总是一对矛盾。我们的目的是要用有限的空间装入最优价值的东西。
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights
associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the
complete item, or don’t pick it (0-1 property).
A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.
1) Optimal Substructure:
To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).
If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.
2) Overlapping Subproblems
Following is recursive implementation that simply follows the recursive structure mentioned above.
package DP;
public class ZeroOneKnapsack {
public static void main(String[] args) {
int[] wt = {10, 20, 30};
int[] val = {60, 100, 120};
int cap = 50;
int n = wt.length;
System.out.println(knapSackRec(cap, wt, val, n));
System.out.println(knapSackDP(cap, wt, val, n));
}
// Returns the maximum value that can be put in a knapsack of capacity cap
public static int knapSackRec(int cap, int[] wt, int[] val, int n){
if(n==0 || cap==0){
return 0;
}
// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if(wt[n-1] > cap){
return knapSackRec(cap, wt, val, n-1);
}else{ // Return the maximum of two cases: (1) not included (2) nth item included
return Math.max(knapSackRec(cap, wt, val, n-1),
knapSackRec(cap-wt[n-1], wt, val, n-1) + val[n-1]);
}
}
public static int knapSackDP(int cap, int[] wt, int[] val, int n){
int[][] dp = new int[n+1][cap+1];
for(int i=0; i<=n; i++){
for(int w=0; w<=cap; w++){
if(i==0 || w==0){
dp[i][w] = 0;
}else if(wt[i-1] > w){ // 因为超重了,所以不选
dp[i][w] = dp[i-1][w];
}else{ // 挑不选和选之间价值更大一个
dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-wt[i-1]]+val[i-1]);
}
}
}
return dp[n][cap];
}
}
分享到:
相关推荐
动态规划解决0-1背包问题-0-1 knapsack problem.zip
动态规划解决0-1背包问题-0-1 knapsack problem.rar
0-1背包问题的动态规划求解算法, 0-1背包不同于背包问题
0-1背包问题算法研究,武燕,谢刚,0-1背包问题(Knapsack Problem,简称KP)是算法设计分析中的经典问题,具有广泛的实际应用背景。本文首先介绍了什么是0-1背包问题,接着
模拟退火解决0-1背包问题,初学者可以借鉴
0-1背包问题算法实现 #include using namespace std; //--------------------------------------------------------------------------- void Knapsack(int v[],int w[],int c,int n,int m[][10]) { int jMax = ...
背包问题是一个经典的组合优化问题,通常分为0-1背包问题和分数背包问题两种形式。 1. **0-1背包问题**: 在这个问题中,给定一个背包的容量和一组物品,每个物品有自己的重量和价值。目标是决定哪些物品应该放入...
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最...
这是一个简单的0-1背包问题,采用matlab编程,使用模拟退火算法求解,结果精确快速,并可以应用到很多其他问题
该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解0-1背包问题。 0-1 背包问题描述如下:给定n 种物品和一个背包。物品i的重量是wi,其价值为vi ,背包的容量为C。应如何选择装入背包的...
0-1-knapsack-problem-master (10)c.zip
<img src="https://raw.githubusercontent.com/Yuqunyi/Knapsack-problem/main/image/picture1.png" width="450px"> ## 2. 具体算法设计 + **贪心算法** ①求分数背包问题最优解,其思想是求出每个物品的单位价值...
本文实例讲述了C#使用动态规划解决0-1背包问题的方法。分享给大家供大家参考。具体如下: // 利用动态规划解决0-1背包问题 using System; using System.Collections.Generic; using System.Linq; using System.Text...
0-1-knapsack-problem-master (43).zip
0-1-knapsack-problem-master (42).zip
0-1-knapsack-problem-master (41).zip
0-1-knapsack-problem-master (40).zip
0-1-knapsack-problem-master (39).zip
0-1-knapsack-problem-master (38).zip