Description

?試設(shè)計一個用回溯法搜索子集空間樹的函數(shù)。該函數(shù)的參數(shù)包括結(jié)點(diǎn)可行性判定函數(shù)和上界函數(shù)等必要的函數(shù)，并將此函數(shù)用于解0-1背包問題。 0-1 背包問題描述如下：給定n 種物品和一個背包。物品i 的重量是wi?，其價值為vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大? 在選擇裝入背包的物品時，對每種物品i只有2 種選擇，即裝入背包或不裝入背包。不能將物品i 裝入背包多次，也不能只裝入部分的物品i。

Input

第一行有2個正整數(shù)n和c。n是物品數(shù)，c是背包的容量。接下來的1 行中有n個正整數(shù)，表示物品的價值。第3 行中有n個正整數(shù)，表示物品的重量。?

Output

將計算出的裝入背包物品的最大價值和最優(yōu)裝入方案輸出。第一行輸出為：Optimal value is

Sample Input

5 10 6 3 5 4 6 2 2 6 5 4

Sample Output

Optimal value is 15 1 1 0 0 1

HINT

?

?

#include <iostream>
#include<cmath>
#include<cstring>
using namespace std;
int v[100],w[100],dp[100][100],c[100];
int main(){
int n,m;
cin>>n>>m;
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
cin>>v[i];
for(int i=0;i<n;i++)
cin>>w[i];
for(int i=w[0];i<=m;i++)
dp[0][i]=v[0];
for(int i=1;i<n;i++)
for(int j=m;j>=w[i];j--)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
//for(int i=0;i<n;i++){
//for(int j=0;j<=m;j++){
// cout<<dp[i][j]<<" ";
//}
//cout<<endl;}
cout<<"Optimal value is"<<endl;
cout<<dp[n-1][m]<<endl;
for(int i=n-1;i>=1;i--)
{
if(dp[i][m]!=dp[i-1][m])
{c[i]=1; m-=w[i];}
else c[i]=0;
}
if(m!=0)c[0]=1;
else c[0]=0;
cout<<c[0];
for(int i=1;i<n;i++)
cout<<" "<<c[i];
cout<<endl;
return 0;}

轉(zhuǎn)載于:https://www.cnblogs.com/lengxia/p/4460061.html

總結(jié)

以上是生活随笔為你收集整理的ytu 2335: 0-1背包问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。