資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學求解0-1揹包問題的C++程式
在0-1揹包問題中，給出一組物品，每件物品都有重量和價值。我們需要確定在集合中包含每個物品的數量，使總重量小於或等於給定的限制，並且總價值儘可能大。
輸入
Value = [10, 20, 30, 40, 60, 70] Weight=[1, 2, 3, 6, 7, 4] int w=7
輸出
knapsack value is: 100
演算法
Begin
Input: set of items each with a weight and a value
Set knapsack capacity
Number of items=sizeof(values) / sizeof(values[0])
Knapsack(Values (stored in array v), Weights (stored in array w), Number of
distinct items (n), Knapsack capacity W)
If (w < 0)
Return
If no items left or capacity becomes 0
Return 0
Include current item n in knapSack (v[n]) and recurs for
remaining items (n - 1) with decreased capacity (W - w[n])
Exclude current item n from knapSack and recurs for
remaining items (n - 1)
Return maximum value we get by including or excluding current item
End範例程式碼
#include <iostream>
#include <climits>
using namespace std;
int knapSack(int v[], int w[], int n, int W) {
if (W < 0)
return INT_MIN;
if (n < 0 || W == 0)
return 0;
int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
int ex = knapSack(v, w, n - 1, W);
return max (in, ex);
}
int main() {
int v[] = { 10, 20, 30, 40, 60, 70 };
int w[] = { 1, 2, 3, 6, 7, 4 };
int W = 7;
int n = sizeof(v) / sizeof(v[0]);
cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
return 0;
}輸出
Knapsack value is 100
更新於：2019年7月30日
5K次瀏覽
廣告