1940 - 0-1 背包问题（动态规划）
时间限制 : 1 秒
内存限制 : 128 MB
给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？
在选择装入背包的物品时，对每种物品i只能有两种选择，装入或者不装入，不能装入多次，也不能部分装入。
题目输入
第一行输入物品的个数n。
第二行输入物品的重量序列w。(中间有空格）
第三行输入物品的价值序列v。（中间有空格）
第四行输入背包容量c。
题目输出
第一行输出装入背包的物品。（用0和1表示，中间无空格）
第二行输出最大价值。
输入/输出样例
输入格式
3 3 4 5 4 5 6 10
输出格式
011 11
C语言解答
#include <stdio.h> #define max 20 int n,c,w[max],v[max],m[max][max]={0}; void knapsack() { int i,j; for (i=1; i<=n; i++) for (j=1; j<=c; j++) { m[i][j]=m[i-1][j]; if ( j>=w[i-1] && m[i-1][j-w[i-1]]+v[i-1]> m[i][j] ) m[i][j]=m[i-1][j-w[i-1]]+v[i-1]; } } void disp( ) { int i,j; int x[max]={0}; i=n; while ( m[i][c]==m[i-1][c] ) i--; while (i>1) { j=i-1; while (m[i][c]-m[j][c]!=v[i-1] && j>0) j--; x[i]=1; i=j; } for(i=2;i<=n;i++) printf("%d",x[i]); } int main( ) { int i,j; scanf("%d",&n); for (i=0; i<n; i++) scanf("%d",&v[i]); for (i=0; i<n; i++) scanf("%d",&w[i]); scanf("%d",&c); knapsack(); disp(); printf("\n"); printf("%d\n",m[n][c]); return 0; }
C++解答
#include<iostream> using namespace std; int V[200][200]; int max(int a,int b) { if(a>=b) return a; else return b; } int p(int n,int w[],int v[],int x[],int C) { int i,j; for(i=0;i<=n;i++) V[i][0]=0; for(j=0;j<=C;j++) V[0][j]=0; for(i=0;i<=n-1;i++) for(j=0;j<=C;j++) if(j<w[i]) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]); j=C; for(i=n-1;i>=0;i--) { if(V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } for(i=1;i<n;i++) { cout<<x[i]; } cout<<"\n"; return V[n-1][C]; } int main() { int s; int w[15]; int v[15]; int x[15]; int n,i; int C; n=5; cin>>n; for(i=0;i<n;i++) cin>>v[i]; for(i=0;i<n;i++) cin>>w[i]; cin>>C; s=p(n,w,v,x,C); cout<<s<<"\n"; }
Java解答
import java.util.Scanner; //本程序取自王晓东编著“算法分析与设计”第 92 页，例 //0-1背包问题动态规划解法 class Math { public Math() { } static int min(int i, int j) { if (i > j) { return j; } else { return i; } } static int max(int i, int j) { if (i > j) { return i; } else { return j; } } } public class Main { public static void knapsack(int[] v, int[] w, int c, int[][] m) { int n = v.length - 1; int jMax = Math.min(w[n] - 1, c); for (int j = 0; j <= jMax; j++) { m[n][j] = 0; } for (int j = w[n]; j <= c; j++) { m[n][j] = v[n]; } for (int i = n - 1; i > 1; i--) { jMax = Math.min(w[i] - 1, c); for (int j = 0; j <= jMax; j++) { m[i][j] = m[i + 1][j]; } for (int j = w[i]; j <= c; j++) { m[i][j] = Math.max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]); } } m[1][c] = m[2][c]; if (c >= w[1]) { m[1][c] = Math.max(m[1][c], m[2][c - w[1]] + v[1]); } } public static void traceback(int[][] m, int[] w, int c, int[] x) { int n = w.length - 1; for (int i = 0; i < n; i++) { if (m[i][c] == m[i + 1][c]) { x[i] = 0; } else { x[i] = 1; c -= w[i]; } } x[n] = (m[n][c] > 0) ? 1 : 0; } public static void main(String args[]) { // int c1 = 10; Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int v1[] = new int[n];//{0,6, 3, 5, 4, 6}; int w1[] = new int[n];//{0,2, 2, 6, 5, 4}; for(int i=0;i<n;i++) { v1[i]=sc.nextInt(); } for(int i=0;i<n;i++) { w1[i]=sc.nextInt(); } int c1 = sc.nextInt(); // System.out.print("v1[]={"); // for (int i = 0; i < v1.length; i++) { // System.out.print(v1[i]); // } // System.out.print("}"); // System.out.println(); // System.out.print("w1[]={"); // for (int i = 0; i < w1.length; i++) { // System.out.print(w1[i]); // } // System.out.print("}"); // System.out.println(); // System.out.println("c=" + c1); int n1 = v1.length - 1; int x1[] = new int[n1 + 1]; int[][] m1 = new int[n1 + 1][c1 + 1]; knapsack(v1, w1, c1, m1); traceback(m1, w1, c1, x1); for (int i = 1; i <= n1; i++) { // if (x1[i] == 1) { System.out.print(x1[i]); // } } System.out.println(); System.out.println(m1[1][c1]); } }