Question

数据结构背包问题，希望大神给代码添加注解，越详细越好，跪求，非常急

数据结构背包问题，希望大神给代码添加注解，越详细越好，跪求，非常急

Answer 1

#include<stdio.h>#include<stdlib.h>
//该函数首先尝试将最后一件物品放入背包，则物品减少一件，背包可用体积相应减少，然后对当前状态进行递归……
//若有解则递归结束；若无解则抛弃最后一件物品，然后对当前状态进行递归……
int knap(int s, int n, int w[]) {
if ( s == 0 )
return (1);
else if ( s<0 || s>0 && n<1 )
return(0);
else if ( knap(s - w[n-1], n - 1, w)==1 ) { //从后往前装，如果装满第n个包，剩余的重量仍然可以在剩余的n-1包中放下，那么就将第n个包装满。
printf("result: n=%d ,w[%d]=%d \n", n, n-1, w[n-1]);
return (1);
}
else
return ( knap(s, n - 1, w) );//如果装满第n个包后，剩余的重量不能在剩余的n-1包中放下，那么就不用第n个包，考虑能不能用第n-1个包。
}
//s:背包的重量 n:物品的数量 w[]:每件物品的重量
int main() {
int* w;
int s = 0, n = 0, result = 0, i = 0;
printf("please input s = ");/*输入s*/
scanf("%d", &s);
printf("please input n = ");/*输入n*/
scanf("%d", &n);
w = (int*)malloc(n*sizeof(int));
printf("please input the %d numbers(weight):\n", n);/*输入重量*/
for (i = 0; i < n; i++)
scanf("%d", w+i);
result = knap(s, n, w);
if (result == 0)
printf("no solution!\n");
return 0;
}