以下是可行的0-1背包问题解决方案:
- 使用‘浮点数’表示正值和
- 使用‘浮点数’表示重量(可以为正数或负数)
- 使用‘浮点数’表示背包容量 > 0
这是一个相对简单的二进制程序。
我建议使用剪枝的暴力破解法。如果你超过了允许的重量,就不需要尝试其他物品的组合,可以放弃整个树。
哦,等等,你有负重吗?总是包括所有负重,然后按上述方法处理正重量。或者负重物品也有负价值吗?
包括所有带有正价值的负重物品。排除所有带有正重量和负价值的物品。
对于负重物品带有负价值的情况,减去它们的重量(增加背包容量),并使用一个代表不取该物品的伪物品。该伪物品将具有正重量和价值。采用剪枝的暴力破解法进行处理。
class Knapsack
{
double bestValue;
bool[] bestItems;
double[] itemValues;
double[] itemWeights;
double weightLimit;
void SolveRecursive( bool[] chosen, int depth, double currentWeight, double currentValue, double remainingValue )
{
if (currentWeight > weightLimit) return;
if (currentValue + remainingValue < bestValue) return;
if (depth == chosen.Length) {
bestValue = currentValue;
System.Array.Copy(chosen, bestItems, chosen.Length);
return;
}
remainingValue -= itemValues[depth];
chosen[depth] = false;
SolveRecursive(chosen, depth+1, currentWeight, currentValue, remainingValue);
chosen[depth] = true;
currentWeight += itemWeights[depth];
currentValue += itemValues[depth];
SolveRecursive(chosen, depth+1, currentWeight, currentValue, remainingValue);
}
public bool[] Solve()
{
var chosen = new bool[itemWeights.Length];
bestItems = new bool[itemWeights.Length];
bestValue = 0.0;
double totalValue = 0.0;
foreach (var v in itemValues) totalValue += v;
SolveRecursive(chosen, 0, 0.0, 0.0, totalValue);
return bestItems;
}
}
currentCount
参数和一个countLimit
字段。 - Ben Voigt好的,采用暴力破解方式。虽然这是一个NP完全问题,但由于您要处理的数据量不到10个,因此使用暴力破解并不会出现问题。
var size = 10;
var capacity = 0;
var permutations = 1024;
var repeat = 10000;
// Generate items
float[] items = new float[size];
float[] weights = new float[size];
Random rand = new Random();
for (int i = 0; i < size; i++)
{
items[i] = (float)rand.NextDouble();
weights[i] = (float)rand.NextDouble();
if (rand.Next(2) == 1)
{
weights[i] *= -1;
}
}
// solution
int bestPosition= -1;
Stopwatch sw = new Stopwatch();
sw.Start();
// for perf testing
//for (int r = 0; r < repeat; r++)
{
var bestValue = 0d;
// solve
for (int i = 0; i < permutations; i++)
{
var total = 0d;
var weight = 0d;
for (int j = 0; j < size; j++)
{
if (((i >> j) & 1) == 1)
{
total += items[j];
weight += weights[j];
}
}
if (weight <= capacity && total > bestValue)
{
bestPosition = i;
bestValue = total;
}
}
}
sw.Stop();
sw.Elapsed.ToString();
if ((i >> j) & 1)
替换 if (splitOut[j] == '1')
,我相信在C#中语法也类似。 - j_random_hacker如果您只能使用正值,则每个具有负重量的项目都必须进入。
然后,我想你可以计算价值/重量比,并基于该顺序强制执行其余组合,一旦找到适合您的组合,就可以跳过其余部分。
问题可能是评分和排序实际上比进行所有计算更昂贵。
显然,基于集合的大小和分布,将会有不同的盈亏平衡点。
public class KnapSackSolver {
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
int[] profit = new int[N + 1];
int[] 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);
}
// 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++) {
// don't take item n
int option1 = opt[n - 1][w];
// take item n
int option2 = Integer.MIN_VALUE;
if (weight[n] <= w)
option2 = profit[n] + opt[n - 1][w - weight[n]];
// select better of two options
opt[n][w] = Math.max(option1, option2);
sol[n][w] = (option2 > option1);
}
}
// 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]);
}
}
}
这个问题可以通过动态规划来解决。下面的代码可以帮助您使用动态规划解决0/1背包问题。
internal class knapsackProblem
{
private int[] weight;
private int[] profit;
private int capacity;
private int itemCount;
private int[,] data;
internal void GetMaxProfit()
{
ItemDetails();
data = new int[itemCount, capacity + 1];
for (int i = 1; i < itemCount; i++)
{
for (int j = 1; j < capacity + 1; j++)
{
int q = j - weight[i] >= 0 ? data[i - 1, j - weight[i]] + profit[i] : 0;
if (data[i - 1, j] > q)
{
data[i, j] = data[i - 1, j];
}
else
{
data[i, j] = q;
}
}
}
Console.WriteLine($"\nMax profit can be made : {data[itemCount-1, capacity]}");
IncludedItems();
}
private void ItemDetails()
{
Console.Write("\nEnter the count of items to be inserted : ");
itemCount = Convert.ToInt32(Console.ReadLine()) + 1;
Console.WriteLine();
weight = new int[itemCount];
profit = new int[itemCount];
for (int i = 1; i < itemCount; i++)
{
Console.Write($"Enter weight of item {i} : ");
weight[i] = Convert.ToInt32(Console.ReadLine());
Console.Write($"Enter the profit on the item {i} : ");
profit[i] = Convert.ToInt32(Console.ReadLine());
Console.WriteLine();
}
Console.Write("\nEnter the capacity of the knapsack : ");
capacity = Convert.ToInt32(Console.ReadLine());
}
private void IncludedItems()
{
int i = itemCount - 1;
int j = capacity;
while(i > 0)
{
if(data[i, j] == data[i - 1, j])
{
Console.WriteLine($"Item {i} : Not included");
i--;
}
else
{
Console.WriteLine($"Item {i} : Included");
j = j - weight[i];
i--;
}
}
}
}
import java.util.*;
class Main{
static int max(inta,int b)
{
if(a>b)
return a;
else
return b;
}
public static void main(String args[])
{
int n,i,cap,j,t=2,w;
Scanner sc=new Scanner(System.in);
System.out.println("Enter the number of values ");
n=sc.nextInt();
int solution[]=new int[n];
System.out.println("Enter the capacity of the knapsack :- ");
cap=sc.nextInt();
int v[]=new int[n+1];
int wt[]=new int[n+1];
System.out.println("Enter the values ");
for(i=1;i<=n;i++)
{
v[i]=sc.nextInt();
}
System.out.println("Enter the weights ");
for(i=1;i<=n;i++)
{
wt[i]=sc.nextInt();
}
int knapsack[][]=new int[n+2][cap+1];
for(i=1;i<n+2;i++)
{
for(j=1;j<n+1;j++)
{
knapsack[i][j]=0;
}
}
/*for(i=1;i<n+2;i++)
{
for(j=wt[1]+1;j<cap+2;j++)
{
knapsack[i][j]=v[1];
}
}*/
int k;
for(i=1;i<n+1;i++)
{
for(j=1;j<cap+1;j++)
{
/*if(i==1||j==1)
{
knapsack[i][j]=0;
}*/
if(wt[i]>j)
{
knapsack[i][j]=knapsack[i-1][j];
}
else
{
knapsack[i][j]=max(knapsack[i-1][j],v[i]+knapsack[i-1][j-wt[i]]);
}
}
}
//for displaying the knapsack
for(i=0;i<n+1;i++)
{
for(j=0;j<cap+1;j++)
{
System.out.print(knapsack[i][j]+" ");
}
System.out.print("\n");
}
w=cap;k=n-1;
j=cap;
for(i=n;i>0;i--)
{
if(knapsack[i][j]!=knapsack[i-1][j])
{
j=w-wt[i];
w=j;
solution[k]=1;
System.out.println("k="+k);
k--;
}
else
{
solution[k]=0;
k--;
}
}
System.out.println("Solution for given knapsack is :- ");
for(i=0;i<n;i++)
{
System.out.print(solution[i]+", ");
}
System.out.print(" => "+knapsack[n][cap]);
}
}