#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int limit_weight,best_value,best_weight,jjj;
int Nnum,branch;
struct Item{
    int weight;
    int value;
}item[100];
int insert_num[100],best_ans_num[100];

int item_cmp(const void *a, const void *b){
    if(((struct Item *)a)->value/(double)((struct Item *)a)->weight >= ((struct Item *)b)->value/(double)((struct Item *)b)->weight)
        return -1;
    else return 1;
}

int get_bound(int deep,int weight,int value){//上界値の計算

    for(;deep < Nnum && limit_weight > weight + item[deep].weight;deep++){
        weight += item[deep].weight;
        value += item[deep].value;
    }
    return value + item[deep].value*(limit_weight-weight)/item[deep].weight;
}
void search(int deep,int weight,int value){
    branch++;
    if(deep < Nnum){
        /*この下３ヶ所のコメントを外すと枝刈できる*/
        //if(best_value < get_bound(deep,weight,value)){
            insert_num[deep] = 1;
        //  if(weight + item[deep].weight <= limit_weight) 
            search(deep+1,weight+item[deep].weight,value+item[deep].value);
            insert_num[deep] = 0;
            search(deep+1,weight,value);
        //}
    }
    else{
        if(limit_weight >= weight && value > best_value){
            best_value = value;
            best_weight = weight;
            memcpy(best_ans_num,insert_num,sizeof(int)*Nnum);
        }
    }
}
int main(){
    int i;
    scanf("%d",&limit_weight);
    for(Nnum=0;Nnum < 100 && scanf("%d %d",&item[Nnum].weight,&item[Nnum].value) != EOF;Nnum++);
    qsort(item,Nnum,sizeof(struct Item),item_cmp);

    search(0,0,0);
    
    printf("アイテム数%d\nナップザック容量 %d\n袋に入れるアイテム\n",Nnum,limit_weight);
    for(i = 0;i < Nnum;i++) if(best_ans_num[i]) printf("重量=%d 価値=%d\n",item[i].weight,item[i].value);
    printf("合計重量 %d\n合計価値 %d\n",best_weight,best_value);
    printf("分岐した枝の数 %d\n",branch);
    return 1;
}

プログラムはファイルからリダイレクトで読みこみ。最初に
ナップザック容量
次に
アイテム重量 アイテム価値
がアイテムの数続く
例↓容量50　アイテム10個

50
10 5
7 3
4 4
15 9
6 10
20 8
6 5
13 7
25 18
1 2

関係ないけど、こないだ最長経路のプログラムでウソプログラム書いちゃったなぁ…