//该方法是使用的记忆搜索的方法，请自行简化。 Int rec( int I , int j){ int res; if(i==n){ res=0; //表明物品已经放完了。 }else if(j<w[i]){ res=rec(i+1,j);//此时包内的空间不够放下第I个物品。 }else{ res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); // 进行比较，如果放入物品的价值比原来已经放入物品的总价 值高，则替换原来的 } dp[i][j]=res; return dp[i][j]; }
4 0 3 5>3 6>4 6>5
5 0 3 5>3 6>4 7>6
0 1 2 3 4
所以这些单元格里面都填入0， 即价值为0
当空间为1的时候，只能放下 一件价值为2的物品
Dp[i+1][j-w[i]]+v[i]
整体来说，需要考虑的是： 1、当前包内所占用的空间和总的价值。 2、如果我把当前的物品不放进包里，那么包内的价值会保持 上一次操作的结果。 3、如果，我把当前的物品放进包内会发生什么变化：我要把 当前物品放进去，肯定要给他足够的空间，如果空间不够，自 然是放不进去的，如果空间够了，那么我会把之前放入的物品 拿出来一些，为当前的物品腾出空间。但是这时，我就得判断 一下，我把当前物品放进去后，包内的总价值是不是比原来的 高，（也可以这样考虑，我拿出的那一部分物品的价值是不是 比当前物品的价值要高）如果不是，那么我就无需把当前的物 品放进去了，因为得不到我想要的结果。如果是，就放进去。
#include<iostream> using namespace std; #include<iostream> using namespace std; int n,W; int w[10],v[10]; int dp[10][10]; int max(int x,int y){ if(x>y)return x; else return y; } void slove(){ cout<<rec(0,W); } int main(){ cout<<"please enter n and W:"; cin>>n>>W; for(int i=0;i<n;i++){ cin>>w[i]>>v[i]; } slove(); return 0; }
01背包问题——动态规划 首先给出数据：物品的个数是4，w , v分别为(2,3),(1,2),(3,4),(2,2);背包容量为5
表示背包没有空间可以放东西
i/j
表 示 没 有 物 品 放 入
0 0 0 0Байду номын сангаас0 0
1 0 0 2 2 2
2 0 3 3>2 3>2 3>2
3 0 3 5>3 5>4 5>4