分組背包問題（六）
一問題描述：
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。
這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。
求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
二 解決辦法：
第k組解決辦法如下：
f[k][v] = max(f[k-1][v] , f[k-1][v-c[i]] + w[i])
for(int k = 0 ; k < K ; k++)
for(int v = V ; v >= 0 ; v--) //將每一個分組當做一次01背包 ,故計算順序為V遞減
for(每一個分組中的i)
f[v] = max(f[v] , f[v-c[i]] + w[i])
三 代碼分析：
#include <iostream>
using namespace std ;
const int V = 1000 ;
const int T = 3 ;
const int K = 2 ;
int w[K][T] = 
{
{5 , 10 , 8} ,
{15 , 20 , 15}
} ;
//表示每一種物品的價值
int c[K][T] = {
{200 , 300 , 400} ,
{400 , 800 , 200}
} ; //表示每一種物品的體積
int f[V + 1] ; //
int package()
{
for(int i = 0 ; i<=V ;i++) //表示背包中可以不需要裝滿
f[i] = 0 ;
for(int k = 0 ; k < K ;k++)
{
for(int v = V ; v >= 0 ;v--) //將每一個分組當做一次01背包 ,故計算順序為V遞減
{
for(int i = 0 ; i < T ;i++) //針對每一個分組中的每一個i
{
if(v - c[k][i] >= 0)
f[v] = max(f[v] , f[v - c[k][i]] + w[k][i]) ;
}
}
}
return f[V] ;
}
int main()
{
int temp = package() ;
cout<<temp<<endl ;
getchar() ;
return 0 ;
}