动态规划-0-1背包问题

#include<stdio.h> #define N 4 //物品数量 #define M 5 // 背包容量 int max(int a,int b) { return a>b?a:b; } int main() { int W[] = {0,1,2,3,4}; //物品重量(后期扣除容量的) int v[] = {0,2,4,5,6};//物品价值 int i,j; int f[N+1][M+1] = {0};//子问题解的数组 for(i = 1;i<=N;i++) { for(j = 1;j<=M;j++) { //不选择当前第i个物品 f[i][j] = f[i-1][j]; if(j>=W[i]) { //选择当前第i个物品，但是需要与i-1的物品比较择优价值 f[i][j] = max(f[i][j],f[i-1][j-W[i]]+v[i]); } } } printf("%d\n",f[N][M]); for(i = 1;i<=N;i++) { for(j = 1;j<=M;j++) { printf("%d ",f[i][j]); } printf("\n"); } }