ほかのスレにあったのですが、考え方としてダメ？２５８じゃなけど
#include　<stdlib.h>
#define　LEN　5
#define　MAX　8　

struct　NIMOTU　{
　　char　name;　　char　used;　　int　size;　　　int　points;　
}　data[LEN]={{'a',0,4,450},{'b',0,5,570},{'c',0,2,225},{'d',0,1,110},{'e',0,6,670}};

char　solution[LEN];
int　　max_points　=　-1;
int　　max_size　=　0;

int　less(const　void　*x,　const　void　*y) {
　　int　n,　m;
　　if　((n　=　((struct　NIMOTU　*)　x)->size)　<=　0)　n　=　1;
　　if　((m　=　((struct　NIMOTU　*)　y)->size)　<=　0)　m　=　1;
　　return　((struct　NIMOTU　*)　y)->points/m　-　((struct　NIMOTU　*)　x)->points/n;
}

int　eval(int　i,　int　rest) {
　　int　j,　s = 0;
　　for　(j　=　i;　j　<　LEN;　j++)
　　　　if　(data[j].size　<=　rest)
　　　　　　s　+=　data[j].points;
　　return　s;
}

void　knap(int　i,　int　size,　int　points) {
　　int　j;
　　if　(points　+　eval(i,　MAX　-　size)　<=　max_points)　{
　　　　return;
　　}
　　if　(max_points　<　points)　{
　　　　max_points　=　points;
　　　　max_size　=　size;
　　　　for　(j　=　0;　j　<　LEN;　j++)
　　　　　　solution[j]　=　data[j].used;
　　}
　　if　(i　>=　LEN)
　　　　return;
　　for　(j　=　i;　j　<　LEN;　j++)　{　/*　重複を省く　*/
　　　　if　(size　+　data[j].size　<=　MAX)　{
　　　　　　data[j].used　=　1;　　/*　入れる　*/
　　　　　　knap(i+1,　size　+　data[j].size,　points　+　data[j].points);
　　　　　　data[j].used　=　0;　　/*　出す　*/
　　　　}
　　}
}

int　main() {
　　int　i;
　　qsort(data,　LEN,　sizeof(struct　NIMOTU),　less);
　　knap(0,　0,　0);
　　for　(i　=　0;　i　<　LEN;　i++)
　　　　if　(solution[i])
　　　　　　printf("%c",　data[i].name);
　　printf("\nTotal　size　=　%d,　Total　points　=　%d\n",　max_size,　max_points);
}