给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100)，价值为vi(vi<=100)，背包的容量为C(C<=1000)。
应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。
输入格式:
共有n+1行输入：
第一行为n值和c值，表示n件物品和背包容量c；
接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。
输出格式:
输出装入背包中物品的最大总价值。
输入样例:
在这里给出一组输入。例如：
5 10
2 6
2 3
6 5
5 4
4 6
输出样例:
在这里给出相应的输出。例如：
15
N, V = map(int, input().split())
dp = [0] * (V+1)
for _ in range(N):
v, w = map(int, input().split())
for j in range(V, v-1, -1):
dp[j] = max(dp[j], dp[j-v]+w)
print(dp[-1])
可以做个参考，感觉我这个是最笨的方法。用php写的，输入的没加。
<?php
/*
* $arr 每个物品重量如
*
*
*/
$n=5;
$c=10;//背包总量
//$a<=100;//每个物品重量
//$b<=100;//每个物品价格
//$c<=1000;
$yz=[[2,6],[2,3],[6,5],[5,4],[4,6]];//已知物品重量对应单价数组【重量，总价值】
$r=get_max_jz($n,$yz,$c);
print_r($r);
function get_max_jz($n,$yz,$c){
if($n>100){
return '物品种类不能超出100';
}
if($c>1000){
return '背包容纳不能超出1000';
}
foreach($yz as $k=>$v){
if($v[0]>100){
return '每个物品重量不能超出100';
}
if($v[1]>100){
return '每个物品价值不能超出100';
}
}
$g=get_jz($yz,$n,$c);
foreach($g as $k1 => $v1){
$max_jz[]=$v1['jz'];//价值
$max_qf[]=$k1;//取法
$max_zl[]=$v1['zl'];//当前取法总重量
}
$return['jz']=$jz=max($max_jz);//最大价值
$str='可取得最大价值为'.$jz;
$nn=1;
foreach($g as $k1 => $v1){
if($v1['jz']==$jz){
$return['data'][$k1]=$v1['zl'];
$str .= ',取法'.$nn.'：';
$arr=explode('_',ltrim($k1,'_'));
foreach($arr as $k2=>$v2){
$arr_x=explode('%',$v2);
$str_f=$arr_x[1]?'<span style="color:blue;">✔</span>':'<span style="color:red;">✘</span>';
$str .= '第'.$arr_x[0].'种'.$str_f.',';
}
$str .= '当前取法总重量为'.$v1['zl'].'。';
$nn++;
}
}
$return['xx']=$str;
return $return;
}
//已知数据中取得所有可能值($yz 已知数，$fz 已经放置记录（每个物品的放置记录，0 不放 1 放） $n 物品种类数 ，$yg 已经过的几个)
function get_jz($yz,$n,$c,$yg=0,$fz=[]){
$arr=[];
if(count($fz)){
foreach($fz as $kk=>$vv){
$str = $kk.'_'.($yg+1).'%0';
$str1 = $kk.'_'.($yg+1).'%1';
$arr[$str]=$vv;//当前物种不选时
//选择当前种类，总量不能超过背包容量
if($vv['zl']+$yz[$yg][0]<=$c){
$arr[$str1]['zl']=$vv['zl']+$yz[$yg][0];
$arr[$str1]['jz']=$vv['jz']+$yz[$yg][1];
}
}
if($yg >= ($n - 1)){
return $arr;
}else{
return get_jz($yz,$n,$c,$yg+1,$arr);
}
}else{
$str = '_'.'1%0';
$str1 = '_'.'1%1';
$arr[$str]['zl']=0;
$arr[$str]['jz']=0;
//重量不超过背包容量
if($yz[0][0] <= $c){
$arr[$str1]['zl']=$yz[0][0];
$arr[$str1]['jz']=$yz[0][1];
}
if($yg >= ($n - 1)){
return $arr;
}else{
return get_jz($yz,$n,$c,$yg+1,$arr);
}
}
}