有谁知道吗。。。能谢给我吗。。急求。。。

根据具体情况写，要不你给我来一题。。

好吧。。背包问题 设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为ＸＫ，今从ｎ种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于ＸＫ，而价值的和为最大。
输入数据：
第一行两个数：物品总数Ｎ，背包载重量ＸＫ；两个数用空格分隔；
第二行N个数,为Ｎ种物品重量；两个数用空格分隔；
第三行N个数,为N种物品价值; 两个数用空格分隔；
输出数据：
第一行总价值；
以下N行，每行两个数，分别为选取物品的编号及数量；
输入样例：
4 10
2 3 4 7
1 3 5 9
输出样例：
12
2 1
4 1 
就是要用动态规划思想。。做

周末有空写下。。。

感谢！！！！！！！！！！！！！！！！！

这个NP问题以前没有接触到，比较好理解的是0-1背包问题。
我百度了下完全背包，上面解释还可以，[url=http://baike.baidu.com/view/841810.htm]背包问题(NP),请百度之[/url]
现在没心情研究算法了，lz可以感兴趣的话可以看看，按照别人的思想来实现下，总之对于 动态规划，理解好下面几步就可以了。(摘录)

（1） 把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。
（2） 将问题发展到各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始（边界）条件。
（3） 应用递推求解最优值。
（4） 根据计算最优值时所得到的信息，构造最优解。
    构造最优解就是具体求出最优决策序列。通常在计算最优值时，根据问题具体实际记录更多的信息，根据所记录的信息构造出问题的最优解。 

帖上一段阉割的代码。。希望对lz有帮助
#include <stdio.h>
#define  MAXPAC  20                //定义最大包为20
 
int main(int argc, char *argv[])
{
    /* goods_num 物品数量, pac_bd 背包最大载重, 
       w[]各个物品的重量，p[]各个物品的价值,
       choice[][]用于归纳是否选取物品 i 而得到的价值 */
    
    int goods_num, pac_bd, w[MAXPAC], p[MAXPAC], choice[MAXPAC][MAXPAC];
    
    /* i 为物品列号，from 0 to goods_num, j 为背包剩余载重空间, 
       pac_left意义同 j, 用法见代码的line 63 to line 74*, 
       max_price用法见 line 64 to line 75*/
       
    int index, i, j, pac_left, max_price;
    
    printf("input the num of the goods and the burden of the package: \n");
    scanf("%d%d", &goods_num, &pac_bd);
    
    printf("input the weight of each goods: \n");
    for(index = 0; index < goods_num; ++index)
    {
        scanf("%d", &w[index]);
    } 
    
    printf("input the price of each goods: \n");
    for(index = 0; index < goods_num; ++index)
    {
        scanf("%d", &p[index]);
    }
    /*输入结束*/
    
    /*开始确定边界以及初始化边界值*/
    for(j = 0; j <= pac_bd; ++j)         
    {
        if(j >= w[goods_num - 1])
        {
            choice[goods_num - 1][j] = p[goods_num - 1];
        }
        else
        {
            choice[goods_num - 1][j] = 0;
        }
    }
       
    /*对每一阶段作出决策,这一步是思想的关键*/
    for(i = (goods_num - 1) - 1; i >= 0; --i)       
    {
        for(j = 0; j <= pac_bd; ++j)
        {
            if(j >= w[i] && choice[i + 1][j] < choice[i + 1][j - w[i]] + p[i])
            {
                choice[i][j] = choice[i + 1][j - w[i]] + p[i];
            }    
            else
            {
                choice[i][j] = choice[i + 1][j];
            }
        }
    }
    
    printf("the highest price is : %d\n", choice[0][pac_bd]); //choice[0][pac_bd]即为所求 
    
    pac_left = pac_bd;
    max_price = 0;
     
    for(i = 0; i < goods_num - 1; ++i)                   
    {
        if(choice[i][pac_left] > choice[i + 1][pac_left]) //根据此条件来判断是否被选 
        {
            pac_left  -= w[i];
            max_price += p[i];
            printf("number : %d is chosen .\n", i+1);
        }
    }
    if(max_price + p[goods_num - 1] == choice[0][pac_bd]) //如果最后一个被选则必须满足这个条件 
    {
        printf("number : %d is chosen .\n", goods_num);
    } 
    
    return 0;
}