请用c++完善下列代码:void Knapsack_DP(Item items[], int n, int C) { int i, j, dp[n + 1][C + 1]; bool t[n + 1][C + 1]; // direction of recursion, True means selecting the item int solution[n + 1]; // the collection of items in the solution } bool cmp_value(Item a, Item b){ if(a.val != b.val) return a.val > b.val; return a.size < b.size; } bool cmp_size(Item a, Item b){ if() } bool cmp_density(Item a, Item b){ }
时间: 2023-04-04 20:04:19 浏览: 111
背包问题之贪婪算法求解C语言源代码).rar_greedy_greedy knapsack_knapsack greedy_背包
void Knapsack_DP(Item items[], int n, int C) {
int i, j, dp[n+1][C+1];
bool t[n+1][C+1]; // direction of recursion, True means selecting the item
int solution[n+1]; // the collection of items in the solution
for(i=0;i<=n;i++){
for(j=0;j<=C;j++){
dp[i][j]=0;
t[i][j]=false;
}
}
for(i=1;i<=n;i++){
for(j=1;j<=C;j++){
if(items[i-1].size>j){
dp[i][j]=dp[i-1][j];
}
else{
int val1=dp[i-1][j];
int val2=dp[i-1][j-items[i-1].size]+items[i-1].val;
dp[i][j]=max(val1,val2);
t[i][j]=(val2>val1);
}
}
}
int c=C;
int count=0;
for(i=n;i>=1;i--){
if(t[i][c]){
solution[count++]=i-1;
c-=items[i-1].size;
}
}
printf("The optimal solution is: ");
for(i=count-1;i>=0;i--){
printf("%d ",solution[i]);
}
printf("\n");
}
bool cmp_size(Item a, Item b){
if(a.size != b.size)
return a.size < b.size;
return a.val > b.val;
}
bool cmp_density(Item a, Item b){
if(a.val/a.size != b.val/b.size)
return a.val/a.size > b.val/b.size;
return a.size < b.size;
}
阅读全文